- Model question
Event, causal and global ordering
Short answer
Event ordering uses the happened-before relation: a→b if a precedes b in same process, or a is send and b is receive, or transitive. Causal ordering ensures if m1→m2 then all deliver m1 before m2 (e.g., question before answer). Global ordering ensures all processes deliver all messages in the same order, regardless of causality (e.g., replicated updates applied identically).
Define event ordering, causal ordering, and global ordering with suitable examples.
Event ordering
Event ordering decides in which sequence the events of a distributed system (send, receive, internal events) are considered to have occurred. Within one process events are totally ordered by local time. Between processes, order is defined by the happened-before relation (→): a → b if a precedes b in the same process, or a is a send and b the matching receive, or by transitivity. Events not related by → are concurrent. Example: P1 sends m1 (event a); P2 receives it (event b): a → b. Another event c on P3 with no message exchange is concurrent with both.
Causal ordering
Causal ordering requires that if the multicast of message m1 happened before the multicast of m2 (m1 → m2), then every process delivers m1 before m2. Concurrent messages can be delivered in any order. Implemented with vector clocks. Example: in a discussion forum, a question message Q and its answer A (sent after seeing Q) must be delivered to everybody as Q then A; an answer must never appear before its question.
Global (total) ordering
Global or total ordering requires that all processes deliver all messages in the same order, whether or not the messages are causally related. The order itself may differ from real time. Implemented with Lamport timestamps (ties broken by process id) or a sequencer. Example: two clients simultaneously update replicated account balances (deposit and interest); all replicas must apply the two updates in the same order, else they become inconsistent.
| Ordering | Guarantee |
|---|---|
| FIFO | Messages from one sender delivered in send order |
| Causal | Causally related messages delivered in order |
| Total/global | Same order of delivery at all processes |
Total ordering does not imply causal ordering unless it is built on top of it.
✓ Answer checked by Claude Opus 5.5 (high effort)