Lamport Clock

Motivation

解決在分散式系統中，因為clock drift的關係，無法依賴physical clock來決定event的先後順序，需要一套演算法來決定系統中event的先後順序(total ordering)。

Partial Ordering

Partial ordering的定義如下:

• Reflexivity: a <= a
• Antisymmetry: if a <= b and b <= a => a = b
• Transitivity: if a <= b and b <= c => a <= c

Strict partial orders

• Irreflexivity: not a < a
• Asymmetry: if a < b then not b < a
• Transitivity: if a < b and b < c => a < c

Total Ordering

Partial ordering 加上一個額外的條件:

• strongly connected a <= b and b <= a

Logical Clock

既然沒辦法依靠physical clock，那只好設計一個clock，並且滿足以下條件:

• 如果 event a happened before event b (a -> b)，則 $C(a) < C(b)$ (C是 clock function)

要滿足以上條件，必須滿足兩個sub condition:

• 如果 event a, b 由同一個 $process_i$產生，而且 a 在b之前，則 $C_i(a) < C_i(b)$
• 如果 event a 是由 $P_i$ 送給 $P_j$ 接收 (接收的event 為 b)，則 $C_i(a) < C_j(b)$

以上條件滿足Partial ordering，我們可以藉由加上限制來滿足total ordering： $a => b$ (=> means total ordering) if and only if:

• $C_i(a) < C_j(b)$ or ($C_i(a) = C_j(b)$ $P_i, P_j$ are total ordering)

Lamport Clock

Lamport 提出一個作法，可以滿足以上的條件，演算法非常單純：

1. 每次有新的event，$P_i$ 都會增加Clock的值
2. 假設 $T_m$ (timestamp m) $C_i(a)$的值，收到 event的process 要把 clock value增加到大於 $T_m$

第一個做法保證 $C_i(a) < C_i(b)$，而第二個做法保證了 $C_i(a) < C_j(b)$，所以是滿足了strong clock condition: $C(a) < C(b)$。

Constraints

Lamport clock是CP演算法，概念上是每個node都要維護一樣的順序，存在著一個distributed state matchine，因此不能有node存在不一樣的狀態，因此每個node都必須要收到通知，因此如果有一個node掛了，整個系統就不能在接受新的state transition。