Physical clocks drift, network delay varies, and no process can read a perfect global clock. Cristian’s algorithm and NTP estimate time by exchanging messages, but uncertainty remains. Many protocols need only event order, not wall-clock time.
Happened-before
Lamport defines (a → b) when:
- both events occur in one process and
acomes first; asends a message thatbreceives;- the relation follows transitively.
If neither (a → b) nor (b → a), the events are concurrent.
Lamport clocks increment locally and attach a timestamp to messages. On receive:
clock = max(local_clock, received_clock) + 1They guarantee (a → b ⇒ L(a) < L(b)), but the reverse is false. A lower timestamp does not prove causality.
Vector clocks keep one counter per process. They can distinguish causality from concurrency by component-wise comparison, at the cost of metadata that grows with membership.
In plain terms: Lamport clocks give a sortable receipt number; vector clocks also show whether one event could have known about another.
Multicast order is a contract
| Guarantee | Meaning |
|---|---|
| FIFO | Each sender’s messages arrive in send order |
| Causal | Causally related messages arrive in causal order |
| Total | All recipients deliver messages in the same order |
Total order does not automatically preserve causality, and causal order does not force concurrent messages into one global order. Choose the weakest contract that preserves application correctness.
Reliable multicast adds delivery guarantees despite loss. Virtual synchrony combines multicast with membership views so surviving processes observe consistent delivery around joins and failures.
Review card
- Physical synchronization estimates time; it does not remove uncertainty.
- Happened-before defines causal order.
- Lamport timestamps preserve causality in one direction only.
- Vector clocks detect concurrency but carry larger metadata.
- FIFO, causal, and total order solve different problems.
- Ordering must be defined together with reliability and membership changes.