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.
Physical clock 會 drift、network delay 會變，沒有 process 能讀取完美 global clock。Cristian’s algorithm 與 NTP 用 message exchange 估時間，但 uncertainty 仍存在。許多 protocol 真正需要的是 event order，不是 wall-clock time。
Happened-before
Lamport 定義 (a → b)：
- 兩 event 在同一 process，且
a先發生； asend message，breceive；- relation 具有 transitivity。
若 (a → b)、(b → a) 都不成立，兩者 concurrent。
Lamport clock 在 local event 增加，並把 timestamp 放進 message。Receive 時：
clock = max(local_clock, received_clock) + 1它保證 (a → b ⇒ L(a) < L(b))，反向不成立；timestamp 較小不能證明 causality。
Vector clock 每個 process 保存一個 counter，透過 component-wise comparison 分辨 causality／concurrency，代價是 metadata 隨 membership 成長。
白話來說： Lamport clock 提供可排序的收據號；vector clock 還能看出某 event 是否可能知道另一 event。
Multicast order 是 contract
| Guarantee | 意義 |
|---|---|
| FIFO | 每個 sender 的 message 按 send order deliver |
| Causal | Causally related message 按 causal order deliver |
| Total | 所有 recipient 使用相同 delivery order |
Total order 不自動保存 causality；causal order 也不強迫 concurrent message 進入單一 global order。應選能維持 application correctness 的最弱 contract。
Reliable multicast 處理 loss 下的 delivery guarantee。Virtual synchrony 把 multicast 與 membership view 結合，讓 surviving process 對 join／failure 周圍的 delivery 有一致觀察。
複習卡
- Physical synchronization 只能估時間，不能消除 uncertainty。
- Happened-before 定義 causal order。
- Lamport timestamp 只單向保留 causality。
- Vector clock 可偵測 concurrency，但 metadata 較大。
- FIFO、causal、total order 解決不同問題。
- Ordering 要和 reliability、membership change 一起定義。