Algorithms for Causal Message Ordering in Distributed Systems

Causal message ordering is a partial ordering of messages in a distributed computing environment. It places a restriction on communication between processes by requiring that if the transmission of message mi to process pk necessarily preceded the transmission of message mj to the same process, then the delivery of these messages to that process must be ordered such that mi is delivered before mj. Causal message ordering is either needed or desirable in a variety of distributed algorithms such as fault-tolerant object replication, distributed resource allocation and teleconferencing. In this paper we evaluate several algorithms for ensuring causal message ordering in a distributed system. We analyze the algorithms based on two orthogonal axes of optimization, which are message size overhead and non-causal message latency. The best algorithm in each class is detailed, as is some significant prior art that led to the discovery of these algorithms. The minimum message size overhead achievable is O(1) but at the expense of P ×Tw non-causal latency, where P is the number of processes in the system and Tw is the worst message time between a process and any other process. By contrast, the non-causal latency can be as low as zero, but with a message size overhead of O(P 2).