Saileshwar Krishnamurthy and M Mukund
Report TCS-95-7, School of Mathematics, SPIC Science Foundation, Madras, India (1995)
This paper investigates a solution to the problem of causal ordering in message-passing distributed systems. Causal ordering is the restriction that messages are delivered in a fifo fashion with respect to the global causal order between events in the system. This is stronger than the condition that each local channel is fifo.
In our algorithm, causal ordering is implemented by having each process maintain, as the computation proceeds, its latest information about every other process in the system. To achieve this, messages are tagged with time-stamps. The novel feature of the protocol described here is that it allows for the reuse of time-stamps. Under certain conditions, this permits an implementation of causal ordering using time-stamps that are uniformly bounded.