Message Ordering and Multicast

Group communication delivers a message to a set of processes with specified reliability and ordering guarantees, ranging from FIFO through causal to total order.

Definition

Multicast delivers a single message to every member of a process group; ordering guarantees constrain the relative delivery order of messages, with FIFO preserving per-sender order, causal preserving the happened-before order, and total order delivering all messages in the same sequence at every member.

Scope

This topic covers reliable multicast and the hierarchy of delivery orderings—FIFO, causal, and total (atomic)—their implementations using sequence numbers, logical clocks, and sequencer or token schemes, and the virtual-synchrony model that integrates ordered multicast with consistent group-membership changes. Total-order (atomic) broadcast is shown to be equivalent in power to consensus.

Core questions

• What reliability and ordering guarantees does an application require from group communication?
• How are causal and total delivery orders implemented efficiently?
• Why is total-order broadcast equivalent to consensus?

Key theories

Ordering hierarchy

Delivery orderings form a hierarchy—FIFO is weaker than causal, which is weaker than total order—each enforced by additional metadata such as per-sender sequence numbers, vector timestamps, or a globally agreed sequence.

Virtual synchrony

Virtual synchrony presents group membership changes and multicast messages in a consistent order to all members, so that processes see the same sequence of events and view changes, simplifying replicated-service construction.

Atomic broadcast equals consensus

Total-order (atomic) broadcast and consensus are reducible to each other, so any solution to one yields a solution to the other and both share the same solvability limits under asynchrony and failures.

Clinical relevance

Ordered, reliable multicast is the substrate of state-machine replication, publish-subscribe systems, and replicated databases, where every replica must apply the same updates in the same order to stay consistent.

History

Birman and Joseph introduced virtual synchrony and ordered multicast in the 1980s through the ISIS system; the relationship between atomic broadcast and consensus was clarified in the 1990s, and Defago, Schiper, and Urban's 2004 survey systematized the many total-order algorithms.

Key figures

• Kenneth Birman
• Thomas Joseph
• Andre Schiper
• Leslie Lamport

Seminal works

• birman1987
• defago2004
• lamport1978

Frequently asked questions

What is the difference between causal and total ordering?

Causal ordering only constrains messages that are causally related, leaving concurrent messages free to be delivered in different orders at different processes. Total ordering requires every process to deliver all messages in the identical sequence, which is strictly stronger and as hard as consensus.