到目前為止，我們都假設時鐘同步自然地與真實時間掛鉤。但我們也看到，有時只要所有節點對「現在時間」達成一致就夠了，不必等於真實時間。還可以再進一步：對 make 而言，兩個節點只要同意「input.o 已被新版 input.c 淘汰」即可——重點是追蹤彼此的事件（例如產生了新版 input.c）。這類演算法所用的時鐘，習慣上稱為邏輯時鐘（logical clocks）。

藍波特（Leslie Lamport）在 1978 年的經典論文中指出：時鐘同步是可能的，但不必是絕對的。兩個不互動的行程，時鐘不同步也無妨——不同步既然觀察不到，就不會造成問題。更重要的是，通常要緊的不是所有行程對「幾點」達成一致，而是對事件發生的順序達成一致。在 make 的例子中，重要的是 input.c 比 input.o 新還是舊，而非兩者的絕對建立時間。

藍波特的邏輯時鐘#

為了同步邏輯時鐘，藍波特定義了 **happens-before（先行發生）**關係。a → b 讀作「a happens before b」，意思是所有行程都同意事件 a 先發生、事件 b 後發生。這個關係可在兩種情況下直接觀察到：

1. 若 a 和 b 是同一行程中的事件，且 a 先於 b 發生，則 a → b 為真。
2. 若 a 是某行程送出訊息的事件、b 是另一行程收到該訊息的事件，則 a → b 為真——訊息不可能在送出之前（甚至同時）被收到，傳遞總需要有限且非零的時間。

happens-before 具遞移性：a → b 且 b → c 則 a → c。若兩事件 x、y 發生在不交換訊息（連間接透過第三方也沒有）的不同行程中，則 x → y 不成立，y → x 也不成立——這兩個事件稱為並行（concurrent）：對它們誰先誰後，什麼也不能說（也不需要說）。

我們需要的是一種時間量測方式：為每個事件 a 指定一個所有行程都同意的時間值 C(a)，且滿足：

• 若 a → b，則 C(a) < C(b)。
• 時鐘值 C 只能前進（遞增）、不能倒退；修正只能用加正值，不能用減。

演算法#

考慮三個行程 P1、P2、P3，各自跑在不同機器上、各有自己速率不同的時鐘：P1 的時鐘走了 6 下時，P2 走了 8 下、P3 走了 10 下（各時鐘速率恆定，但因晶體差異而不同）。

• P1 在時刻 6 送訊息 m1 給 P2，到達時 P2 的時鐘讀 16。若訊息內帶著發送時刻 6，P2 會推斷旅程花了 10 個滴答——合理。P2 到 P3 的 m2 花 16 滴答，也還說得通。
• 但 m3 在 P3 的 60 離開、卻在 P2 的 56 到達；m4 從 P2 的 64 出發、在 P1 的 54 到達——這些值顯然不可能，必須加以防止。

藍波特的解法直接來自 happens-before：m3 既然在 60 送出，就必須在 61 或更晚到達。因此每則訊息都攜帶依發送者時鐘的發送時刻；接收者的時鐘若顯示比發送時刻更早的值，就把自己的時鐘快轉到發送時刻加一。如此 m3 改為在 61 到達、m4 在 70 到達。

更精確地表述（這通常屬於中介軟體層的工作，位於網路層與應用層之間）：每個行程 Pi 維護本地計數器 Ci，依下列步驟更新（Raynal and Singhal, 1996）：

1. 執行任何事件（送訊息、把訊息遞交給應用、或其他內部事件）之前，Pi 先執行 Ci ← Ci + 1。
2. Pi 送訊息 m 給 Pj 時，把 m 的時間戳記 ts(m) 設為執行完上一步之後的 Ci。
3. 收到訊息 m 時，Pj 先把本地計數器調整為 Cj ← max{Cj, ts(m)}，再執行第 1 步，然後把訊息遞交給應用。

若還要求「任兩事件的時間絕不相同」，可以把事件所在的行程編號附加在時間的低位端，以小數點隔開：行程 Pi 在時刻 40 的事件蓋上 40.i。令 C(a) 為事件 a 所在行程的計數器值，我們就得到了最初想要的全域時間值的分散式實作。

範例：全序多播#

考慮一個複製到多地的資料庫：銀行為了查詢效能，把帳戶資料庫的副本放在紐約與舊金山，查詢永遠轉給最近的副本；代價是每個更新操作都必須在每個副本上執行。

假設舊金山的客戶要往目前有 1,000 美元的帳戶存入 100 美元；同時紐約的行員發起「加計 1% 利息」的更新。由於底層網路的通訊延遲，兩個更新可能以不同順序到達兩地：舊金山先存款後計息，得到 1,111 美元；紐約先計息後存款，得到 1,110 美元。

問題在於兩個更新操作應該在每個副本上以相同順序執行。先存款還是先計息雖然結果不同，但就一致性而言採哪個順序並不重要——重要的是兩個副本最後完全一樣。這類情況需要全序多播（totally-ordered multicast）：所有訊息以相同順序遞送給每個接收者的多播操作。藍波特的邏輯時鐘可以完全分散式地實作它。

做法如下。考慮一群彼此多播訊息的行程，每則訊息都蓋上發送者當下的（邏輯）時間戳記；多播時概念上也送一份給發送者自己。並假設同一發送者的訊息依發送順序到達、且訊息不遺失。

• 行程收到訊息時，放入依時間戳記排序的本地佇列，並向其他所有行程多播一則確認（acknowledgment）。依藍波特的時鐘調整規則，被確認訊息的時間戳記必低於確認訊息的時間戳記。因此（只要不移除訊息）所有行程最終會擁有相同的本地佇列副本。
• 只有當訊息位於佇列開頭、且已被其他每個行程確認時，行程才把它遞交給應用；此時將它移出佇列，相關的確認也一併丟棄。

因為每個行程的佇列副本相同，所有訊息在每個地方都以相同順序遞交——全序多播於焉建立。

後續章節會看到，全序多播是複製服務的重要工具：讓各副本在每處以相同順序執行相同操作以維持一致。由於各副本本質上是在同一個有限狀態機中走過相同的轉移，這也稱為狀態機複製（state machine replication）（Schneider, 1990）。

向量時鐘#

藍波特的邏輯時鐘讓分散式系統中的所有事件全序化，並保證：若事件 a 先於事件 b 發生，則 C(a) < C(b)。但反過來不行——光比較 C(a) 與 C(b) 說不出 a、b 的關係：C(a) < C(b) 不必然表示 a 真的先於 b 發生。

舉例來說，三個行程互送訊息，令 Tsnd(mi) 為 mi 送出的邏輯時間、Trcv(mi) 為收到的時間。若 m1 由 P2 收到後，P2 才送出 m3，則 m3 的發送可能依賴 m1 的內容——這裡有潛在因果。但同樣有 Trcv(m1) < Tsnd(m2) 的情況中，m2 的發送可能與 m1 的接收毫無關係。

問題在於：藍波特時鐘不捕捉因果關係（causality）。

因果關係可用**向量時鐘（vector clocks）**捕捉：指定給事件 a 的向量時鐘 VC(a) 滿足——若對某事件 b 有 VC(a) < VC(b)，則已知 a 因果先於 b。做法是讓每個行程 Pi 維護一個向量 VCi，滿足兩個性質：

1. VCi[i] 是至今發生在 Pi 的事件數，即 Pi 的本地邏輯時鐘。
2. 若 VCi[j] = k，表示 Pi 知道 Pj 已發生 k 個事件，即 Pi 對 Pj 本地時間的認知。

第一個性質靠 Pi 每發生一個新事件就遞增 VCi[i] 維持；第二個性質靠訊息**捎帶（piggyback）**向量維持。具體步驟：

1. 執行任何事件之前，Pi 先執行 VCi[i] ← VCi[i] + 1。
2. Pi 送訊息 m 給 Pj 時，把 m 的（向量）時間戳記 ts(m) 設為執行完上一步之後的 VCi。
3. 收到訊息 m 時，Pj 對每個 k 調整 VCj[k] ← max{VCj[k], ts(m)[k]}，再執行第 1 步，然後把訊息遞交給應用。

如此一來，若事件 a 的時間戳記為 ts(a)，則 ts(a)[i] − 1 是 Pi 上因果先於 a 的已處理事件數。Pj 收到 Pi 的訊息 m 時，不僅知道 Pi 上有多少事件因果先於 m 的發送；更重要的是，ts(m) 還告訴接收者其他行程上有多少事件先於 m 的發送、而 m 可能因果依賴它們。

強制因果通訊#

利用向量時鐘，可以確保「唯有因果上先於某訊息的所有訊息都已收到，才遞送該訊息」。假設訊息在一個行程群組內多播。這種**因果序多播（causally-ordered multicasting）**比前述全序多播弱：兩則互不相關的訊息，以何種順序遞交給應用我們並不在乎，甚至各地順序不同也行。

此外假設時鐘只在收發訊息時調整：Pi 送訊息時只把 VCi[i] 加 1；收到帶 ts(m) 的訊息時只做逐項取 max 的合併。

現在假設 Pj 收到來自 Pi、向量時間戳記為 ts(m) 的訊息 m。遞交給應用層的動作將被延遲，直到兩個條件都成立：

1. ts(m)[i] = VCj[i] + 1 —— m 是 Pj 期待從 Pi 收到的下一則訊息。
2. 對所有 k ≠ i，ts(m)[k] ≤ VCj[k] —— Pi 送出 m 時所看過的訊息，Pj 都已經看過。

（行程遞交自己送出的訊息不必延遲。）

例如三個行程 P0、P1、P2：P0 在本地時間 (1,0,0) 多播訊息 m；P1 收到後決定送出 m*，而 m* 比 m 更早到達 P2。此時 P2 會延遲 m* 的遞交，直到 m 已收到並遞交給 P2 的應用層為止。