Reduction of timestamp sizes for causal event ordering
Achour Mostéfaoui, Theel · TUbilio (Technical University of Darmstadt) · 1996
Almost all published work on causal ordering mechanisms assumes theoretically unbounded counters for timestamps, thus ignoring the real-world problem that arises if one is actually interested in an operable implementation, since unbounded counters simply cannot be realized. An argument for its justification often encountered states, that the counter size can be chosen such that, although still bounded by the underlying hardware, counters practically do not overflow or wraparound. For instance, using 32 or even 64 bits per counter realizes counters that allow a large number of timestamped messages to be submitted. Unfortunately, this approach leads to a substantial amount of piggybacked control information. For example, using matrix timestamps in a distributed computation involving not more than 50 processes and 32 bits per integer results in a timestamp size of 80000 bits, i.e., almost 10 K-byte must be additionally transmitted through the communication subsystem per message. In this...