深度探秘

為什麼分散式系統裡「現在幾點」這麼難回答

時間，既實用又麻煩

在分散式系統裡，時間 (time) 同時是「實務需求」也是「理論基礎」。

• 實務上：我們希望全世界的電腦能對電子商務交易蓋上一致的時間戳，方便日後稽核。例如一筆交易牽涉到商家的電腦與銀行的電腦，兩邊的事件都要被準確標時。
• 理論上：時間幫助我們理解分散式執行是「怎麼一步步展開」的。

但問題來了：每台電腦都有自己的物理時鐘 (physical clock)，而這些時鐘彼此會偏離，我們無法把它們完美同步。

沒有「宇宙標準鐘」

更深層的困難來自一個事實：宇宙中沒有一個特別的物理時鐘可以讓我們在想測量時間間隔時去參照。愛因斯坦的狹義相對論早就指出，在一個參考系中被判定為「同時」的兩個事件，在另一個相對運動的參考系裡不一定同時。

當然，一般電腦的相對論效應可以忽略（除非你的電腦在太空船上飛）。分散式系統真正的麻煩是更實際的版本：

• 我們沒有能力在不同節點上夠精確地替事件蓋時間戳，
• 因此無法確定任意兩個事件到底誰先誰後、還是同時發生。

這就是本章要面對的核心挑戰。

生活妙喻

一群沒對過錶的探險隊

散落各地、各戴各錶的探險隊

想像一支探險隊，隊員分散在世界各地的山頭，每個人手上戴著一支便宜的手錶。

• 沒有人有「標準時間」，只能看自己的錶。
• 每支錶走得快慢不一（有的一天快幾秒、有的慢幾秒），這就是漂移。
• 就算出發前大家對過時間，幾天後也會各自走偏，這就是偏移。

現在隊長想知道：「阿明在山頂插旗的那一刻，阿華是不是已經抵達基地了？」

如果只看各自的手錶，根本沒辦法可靠回答——因為兩支錶本來就不一致。隊員之間唯一能溝通的方式，是用無線電互相喊話（傳訊息），而訊息傳到對方耳裡也需要一段不固定的時間。

分散式系統就是這支探險隊：節點各有時鐘、只能傳訊息、而且沒有任何一支「正確的錶」可以當裁判。

實用超能力

認得時間問題，才知道該用哪種工具

這個觀念能幫你做什麼

理解「沒有絕對時間」之後，你會知道遇到不同需求要用不同工具：

1. 需要知道事件發生在哪個鐘點（例如交易稽核）→ 必須把時鐘同步到一個權威的外部時間來源（如 UTC）。
2. 只需要知道事件的先後順序（誰因誰果）→ 其實不必知道精確的物理時間，可以改用邏輯時鐘。
3. 需要看整個系統某瞬間的樣子（例如偵測死結、回收垃圾物件）→ 需要拍下一致的全域狀態快照。

為什麼依賴時間的演算法很多

本章後面會看到，許多分散式問題都依賴時鐘同步，例如：

• 用時間戳把交易排序以維持資料一致性
• 檢查送到伺服器的請求是否新鮮（如 Kerberos 認證依賴鬆散同步的時鐘）
• 過濾掉重複的更新

需求 → 對應工具
知道幾點鐘   → 物理時鐘同步 (UTC)
知道誰先誰後 → 邏輯時鐘 / 向量時鐘
看系統全貌   → 全域狀態快照

先看清「我到底需要哪一種時間」，就不會用錯工具。

深度探秘

用事件與歷史描述系統怎麼演進

系統的基本構成

我們把分散式系統看成由 $N$ 個行程組成的集合：$p_1, p_2, \dots, p_N$。

• 每個行程跑在單一處理器上，處理器不共享記憶體。
• 每個行程 $p_i$ 有一個狀態 (state) $s_i$，包含它所有變數的值（必要時也含它影響的本地檔案等）。
• 行程之間只能透過網路傳訊息互動，不能用別的方式（書中的玩笑：就算行程控制機械手臂，也不准互相握手來溝通！）。

什麼是事件

行程執行時會做一連串動作 (action)，每個動作不外乎：

• 傳送或接收一則訊息，或
• 一個改變自身狀態的內部動作（改某些變數的值）。

事件 (event) 就是「一個行程執行單一動作的發生」。

單一行程內的全序

在同一個行程內，事件可以排成一個完整的先後順序 (total ordering)，記為關係 $\rightarrow_i$：

$$e \rightarrow_i e' \iff \text{事件 } e \text{ 在 } p_i \text{ 比 } e' 先發生$$

因為行程跑在單一處理器上，即使它是多執行緒，這個順序也定義得很清楚。把行程 $p_i$ 內依序發生的所有事件串起來，就是它的歷史 (history)：

$$history(p_i) = h_i = \langle e_i^0, e_i^1, e_i^2, \dots \rangle$$

生活妙喻

每個人寫自己的日記

各寫各的日記

把每個行程想成一個人，他隨身帶著一本日記，每做一件事就按順序記一筆：

• 「早上 9 點寄了一封信給小華」（送訊息事件）
• 「收到小明的回信」（收訊息事件）
• 「把存款數字改成 1000」（內部狀態改變事件）

這本日記就是這個人的歷史。同一本日記裡，誰先誰後一目了然，因為都是同一個人按順序寫下的（單一處理器的全序）。

但是——不同人的日記沒有共用的頁碼。小明日記的『第 3 筆』和小華日記的『第 3 筆』完全沒有可比性，因為他們各寫各的、各看各的錶。

而且日記裡也包含『我寄了什麼信、收了什麼信』。為什麼要記這些？因為之後我們想拼湊整個團隊的全貌時，會需要知道『信件還在路上、還沒被收到』這種情況——這就是把通道狀態藏進行程狀態裡的巧思。

實用超能力

用高階動作描述真實應用

把事件對應到真實業務

實務上我們不必把事件描述得很底層，可以依應用選擇高階的動作描述。例如電子商務應用中，事件可能是：

• 「client 送出訂單訊息」
• 「merchant server 把交易寫入 log」

這讓我們能用業務語言來推理系統的演進，而不必陷在位元層級。

模型給我們的三件事

flowchart TD
  A[行程 pi 執行動作] --> B{動作種類}
  B -->|送或收訊息| C[通訊事件]
  B -->|改變變數值| D[內部狀態事件]
  C --> E[記入該行程歷史 hi]
  D --> E
  E --> F[同行程內事件具備全序]

有了「事件、歷史、行程狀態」這套模型，後面我們才能：

1. 替事件標上邏輯時戳來排序（第 3、4 小章）。
2. 把各行程的歷史前綴組合成全域狀態（第 5 小章）。
3. 因為狀態裡含了送收訊息紀錄，所以能推斷通道裡有沒有訊息在飛。

這套詞彙是整章推理的地基。

深度探秘

skew 與 drift：兩種不準

時鐘怎麼運作

作業系統會讀取節點的硬體時鐘值 $H_i(t)$，再縮放並加上偏移量，產生一個軟體時鐘 $C_i(t)$ 來近似真實物理時間 $t$：

$$C_i(t) = \alpha H_i(t) + \beta$$

其中 $\alpha$、$\beta$ 是我們可自由選擇的係數。注意：只有當時鐘解析度（兩次更新之間的間隔）小於事件間隔時，相鄰事件才會得到不同的時戳。

兩種不準

電腦時鐘彼此不會完全一致，主要有兩種現象：

漂移率

漂移率 (drift rate) 是時鐘相對於理想參考鐘，每單位時間累積的偏移變化量。

• 一般石英晶體時鐘約為 $10^{-6}$ 秒/秒 → 每 $1{,}000{,}000$ 秒（約 11.6 天）就差 1 秒。
• 高精度石英鐘約 $10^{-7}$ 到 $10^{-8}$。
• 原子鐘漂移率約 $10^{-13}$，極度精準。

即使再小的週期差，累積上百萬次震盪後也會造成可觀的差距。

生活妙喻

兩支廉價手錶的賽跑

兩支手錶的故事

想像你和朋友各買了一支便宜手錶，出發前對好時間，分頭旅行。

• skew（偏移）：旅途中某一刻你們碰面，發現你的錶是 3:00、他的是 3:02。這 2 分鐘的瞬間差距就是 skew。
• drift（漂移）：原因是你的錶每天快 1 秒、他的每天慢 1 秒。這種走得快慢不同就是 drift。drift 是因，skew 是某一刻看到的果。

即使出發前對得再準，drift 也會讓差距一天天拉大——這就是為什麼分散式時鐘需要定期重新對時。

為什麼會 drift

手錶靠石英晶體震盪計時，但每顆晶體有物理差異，震盪頻率本就略有不同；連溫度變化都會改變同一顆晶體的頻率。設計上可以補償，但消不掉。

而真正『權威的標準錶』是原子鐘——它數的是銫-133 原子在兩個能階之間躍遷的次數，1 秒被定義成 9,192,631,770 個週期，準到幾乎不漂移。

實用超能力

UTC 與閏秒：全世界怎麼對時

UTC 怎麼來的

協調世界時 (UTC) 是國際通用的計時標準：

• 以原子時 (International Atomic Time) 為基礎（用原子鐘的極穩定輸出）。
• 但我們日常用的『秒、年』源自天文時間（地球自轉與公轉）。地球自轉因潮汐摩擦逐漸變慢，導致天文時間與原子時會慢慢對不上。
• 解法：偶爾插入（極少數時候刪除）一個閏秒 (leap second)，讓 UTC 與天文時間保持一致。

怎麼收到 UTC

UTC 訊號由地面電台與衛星廣播：

來源              準確度（相對於完美 UTC）
地面電台（如 WWV）  約 0.1–10 毫秒
GPS 衛星           約 1 微秒

裝了接收器的電腦就能把時鐘同步到這些訊號。

實務啟示

1. 要對到真實鐘點 → 接 UTC 來源（GPS 接收器最準）。
2. 石英鐘會漂移 → 別假設『對過一次就永遠準』，要定期重新同步。
3. 解析度限制 → 若事件比時鐘更新還密集，會拿到相同時戳，無法分先後。

下一小章就會看到，要把時鐘同步到 UTC，到底有哪些演算法。

深度探秘

兩種同步目標，定義不一樣

兩種同步

要替分散式系統的時鐘對時，有兩種不同的目標：

外部同步 (external synchronization)：把時鐘對準權威的外部 UTC 來源 $S$。對某個同步界限 $D > 0$：

$$|S(t) - C_i(t)| < D, \quad i = 1, 2, \dots, N$$

也就是說，時鐘準到界限 $D$ 之內。

內部同步 (internal synchronization)：只要求時鐘彼此一致。對界限 $D > 0$：

$$|C_i(t) - C_j(t)| < D, \quad i, j = 1, 2, \dots, N$$

也就是時鐘互相同意到界限 $D$ 之內。

兩者的關係

• 內部同步不一定外部同步：時鐘可能集體偏離外部時間，但彼此仍一致。
• 反過來成立：若系統外部同步到界限 $D$，則它也內部同步到界限 $2D$（兩個都離 UTC 不到 $D$，彼此最多差 $2D$）。

生活妙喻

教室裡對手錶

對準牆上的鐘 vs 大家彼此對齊

想像一間教室，牆上掛著一個連到原子鐘的『標準大鐘』（這就是 UTC）。

• 外部同步：每個學生都把自己的錶調到跟牆上大鐘差不超過 $D$ 秒。這樣每個人都『準』。
• 內部同步：學生們圍成一圈，互相把錶調到彼此差不超過 $D$ 秒——但沒人去看牆上的鐘。結果大家可能整體都比真實時間快了 5 分鐘，可是『彼此之間』非常一致。

對某些任務（例如『誰先按下搶答鈕』），其實只要彼此一致就夠了，準不準到真實時間反而不重要——這就是內部同步的價值。

為什麼外部 D 會推出內部 2D

如果每個學生都離牆上大鐘不到 $D$，那任兩個學生之間最糟的情況是：一個快了快 $D$、另一個慢了快 $D$，兩人相差最多接近 $2D$。所以『都對準大鐘』自動保證『彼此也夠接近』。

實用超能力

正確性：單調性比準確更重要的時候

時鐘『正確』不等於『準確』

依定義，時鐘不一定要準確 (accurate) 才算正確 (correct)。若目標只是內部同步，正確性只關心時鐘『機制運作正常』，不管它絕對設定對不對。

常見的正確性條件：

1. 硬體時鐘正確：漂移率落在已知界限 $\rho$ 內（禁止正常運作時數值跳動）： $$(1 - \rho)(t' - t) \le H(t') - H(t) \le (1 + \rho)(t' - t)$$
2. 單調性 (monotonicity)：時鐘只能前進，永不倒退：$t' > t \implies C(t') > C(t)$。

單調性為什麼重要：make 的例子

UNIX 的 make 靠比較原始檔與目的檔的修改時間，決定要不要重新編譯。

如果一台時鐘走太快的電腦在『編譯完之後、檔案被改之前』把時鐘往回調，原始檔看起來會像是『在編譯前就被改過』，於是 make 會誤判而不重新編譯——這就是違反單調性的災難。

好消息：我們可以在不改硬體 tick 速率的前提下達成單調性——因為 $C_i(t) = \alpha H_i(t) + \beta$，我們可調整提供給應用的時間更新速率（讓快的時鐘『慢慢追上』而非直接倒退）。

flowchart TD
  A[發現時鐘走太快] --> B{怎麼修}
  B -->|直接往回調| C[違反單調性, make 誤判]
  B -->|放慢更新速率慢慢校正| D[維持單調性, 安全]

不守正確性條件的時鐘叫 faulty（故障）：停止滴答是 crash failure，其他亂跳則是 arbitrary failure（如 Y2K bug 把 2000 變 1900）。

深度探秘

Cristian：用往返時間估計延遲

先看同步系統的理想情況

在同步系統中，訊息傳輸延遲有已知上下界。設最小傳輸時間為 $min$、最大為 $max$，不確定度 $u = max - min$。

• 若收方把時鐘設成 $t + min$，偏移可能高達 $u$；設成 $t + max$ 也一樣。
• 設成中間點 $t + (max + min)/2$，偏移最多只有 $u/2$。

但真實系統大多是非同步的：延遲沒有上界（尤其在網際網路）。

Cristian 方法

Cristian 用一台連到 UTC 來源的時間伺服器 $S$ 做外部同步：

1. 行程 $p$ 送請求 $m_r$，量測往返時間 $T_{round}$，收到含時間 $t$ 的回覆 $m_t$（$t$ 在送出前最後一刻才填入）。
2. 行程把時鐘設成： $$t + \frac{T_{round}}{2}$$ （假設來回各花一半時間。）

準確度

伺服器填入時間的時刻，落在收到回覆前的某個範圍內，寬度為 $T_{round} - 2,min$，所以準確度為：

$$\pm \left( \frac{T_{round}}{2} - min \right)$$

這是機率性 (probabilistic) 的：只有觀察到的往返時間夠短，才能達到所需準確度。多送幾次請求、取最小 $T_{round}$ 可得最準的估計。

生活妙喻

打電話問報時台

Cristian：打電話問時間

想像你打電話到『報時台』問現在幾點：

• 你按下撥號（記下開始時間）。
• 對方說『現在 3 點整』。
• 你掛電話（記下結束時間）。整通電話花了 4 秒，這是往返時間。

你合理假設：去程和回程各花一半（2 秒）。所以對方說『3 點整』時，其實已經過了去程的 2 秒，現在應該是 3 點又 2 秒——於是你把錶設成 3 點 02 秒。

問題：如果這通電話剛好遇上塞線（網路壅塞），來回時間爆增，這個『各一半』的假設就會失準。所以 Cristian 建議多打幾次、取最快的那次——最快通常代表沒塞線，估得最準。

Berkeley：班長收大家的時間再喊調整

Berkeley 換個玩法。教室裡選一位班長（master），他輪流問每位同學（slave）現在幾點：

• 班長扣掉往返時間估出每人的真實時鐘，連自己一起算個平均。
• 但他不直接把『新時間』告訴大家（那又會多一段傳輸延遲），而是告訴每個人『你該往前/往後調幾秒』。

這樣快的鐘和慢的鐘傾向互相抵消。班長還會剔除明顯離譜的讀數，只對差距不大的一群取容錯平均。

實用超能力

兩種方法的取捨與容錯

兩種方法比一比

Cristian 的弱點與補強

• 單點失效：單一時間伺服器掛了就無法同步。補強：用一群同步過的時間伺服器，客戶端多播請求、採用最先回覆者。
• 惡意/錯誤伺服器：回傳假時間會造成大亂。Cristian 假設時間來源會自我檢查；對付惡意干擾要靠認證技術。
• 容錯極限：若 $N$ 個時鐘中有 $f$ 個故障，要讓正確時鐘仍能達成共識需 $N \ge 3f$。

Berkeley 的細節

• 準確度依賴一個名目上的最大往返時間，超過此值的讀數會被剔除。
• 主機掛了可重新選舉新主機接手（見第 15 章），但選舉不保證在有界時間內完成。
• 實驗：15 台電腦可同步到約 20–25 毫秒內。

sequenceDiagram
  participant P as 行程 p
  participant S as 時間伺服器 S
  P->>S: 請求 mr, 開始計時
  S-->>P: 回覆 mt 內含時間 t
  Note over P: 量得往返時間 T_round
  Note over P: 設時鐘為 t 加上 T_round 的一半

深度探秘

為網際網路規模設計的時間服務

NTP 是什麼

Cristian 與 Berkeley 主要用於內網。網路時間協定 (NTP, Network Time Protocol) 則為網際網路規模設計，定義了一套時間服務架構與協定。

NTP 的主要設計目標：

1. 準確同步到 UTC：即使網路延遲大又多變，NTP 用統計技術過濾時間資料、辨別不同伺服器資料的品質。
2. 可靠、能撐過長時間斷線：有冗餘伺服器與冗餘路徑，可重組。
3. 可擴充：服務能擴展到大量客戶與伺服器，讓客戶頻繁重新同步以抵消漂移。
4. 抗干擾：用認證技術確認時間資料來自可信來源，並驗證回覆位址。

同步子網與 stratum

NTP 伺服器組成一個邏輯階層，叫同步子網 (synchronization subnet)，層級稱為 stratum：

• stratum 1（主要伺服器）：直接連到 UTC 時間來源（如無線電鐘），位於根部。
• stratum 2：與主要伺服器同步的次級伺服器。
• stratum 3：與 stratum 2 同步……以此類推。
• 最底層（葉節點）跑在使用者的工作站上。

stratum 數字越大的時鐘通常越不準，因為每經一層同步就引入一次誤差。

生活妙喻

消息一層一層傳的金字塔

從源頭一層層往下傳的時間

把 NTP 想成一座消息金字塔：

• 塔頂（stratum 1）是直接聽到『官方廣播』的人——他們最準。
• 第二層的人從塔頂的人那裡聽消息（stratum 2），第三層再從第二層聽（stratum 3）……
• 你的筆電在最底層，從上面的人那裡輾轉得知時間。

每傳一層，消息就被『傳話遊戲』稍微扭曲一點點——這就是為什麼層級越深、時鐘越不準。

而且這座金字塔很堅韌：

• 如果塔頂某人的『官方廣播收音機』壞了，他可以降級去聽第二層的人（變成 stratum 2）。
• 如果某人平常的消息來源失聯，他可以改聽另一個人。

NTP 怎麼挑要聽誰

NTP 不會盲目相信任何一個來源。它會：

• 對每個對等來源做資料過濾，算出叫『濾波離散度』的統計量，離散度高代表資料不可靠。
• 跨多個對等來源做對等選擇，剔除相對不可靠者。
• 偏好 stratum 較低（離源頭近）、且同步離散度最小的來源。

實用超能力

三種模式與偏移/延遲的估計

三種同步模式

所有模式都用不可靠的 UDP 傳遞訊息。

用四個時戳估偏移與延遲

程序呼叫與對稱模式中，每則訊息夾帶最近事件的時戳。對一對訊息 $m$、$m'$，記錄四個時間 $T_{i-3}, T_{i-2}, T_{i-1}, T_i$。NTP 算出：

• 偏移估計 $o_i = \dfrac{(T_{i-2} - T_{i-3}) + (T_{i-1} - T_i)}{2}$
• 延遲（兩訊息總傳輸時間） $d_i = (T_{i-2} - T_{i-3}) + (T_i - T_{i-1})$

可證明真實偏移 $o$ 滿足 $o_i - \dfrac{d_i}{2} \le o \le o_i + \dfrac{d_i}{2}$，所以 $o_i$ 是偏移估計、$d_i$ 衡量其準確度。

和 Cristian 一樣，NTP 保留最近 8 對 $\langle o_i, d_i \rangle$，挑 $d_i$ 最小的那組來估 $o$。

鎖相迴路

NTP 用鎖相迴路 (phase lock loop) 模型：依觀察到的漂移率調整本地時鐘更新頻率。例如發現時鐘每小時固定快 4 秒，就把頻率稍微調慢補償。

實測準確度：網際網路路徑上數十毫秒，LAN 上約 1 毫秒。

深度探秘

用兩條直覺規則排出因果順序

不靠物理時間排順序

Lamport 指出：既然無法完美同步時鐘，我們不能用物理時間判斷任意兩事件的先後。但我們可以建立一種類似物理因果、適用於分散式系統的順序，叫 happened-before（發生在之前）關係，記為 $\rightarrow$（也叫潛在因果順序 (potential causal ordering)）。

三條規則

它建立在兩個直覺點上，形式化為三條規則：

• HB1：若在同一行程 $p_i$ 內 $e \rightarrow_i e'$，則 $e \rightarrow e'$。（同行程依執行順序）
• HB2：對任何訊息 $m$，$send(m) \rightarrow receive(m)$。（送一定在收之前）
• HB3：傳遞性——若 $e \rightarrow e'$ 且 $e' \rightarrow e''$，則 $e \rightarrow e''$。

所以若 $e \rightarrow e'$，必存在一串事件 $e_1, e_2, \dots, e_n$（$e_1 = e$、$e_n = e'$），相鄰兩個之間不是 HB1 就是 HB2 成立。

並行事件

不是所有事件都有 $\rightarrow$ 關係。若兩事件之間沒有任何因果鏈（既非同行程、也無訊息鏈相連），它們就是並行 (concurrent) 的，記為 $a \parallel e$。

生活妙喻

群組訊息的『已讀回覆』鏈

訊息接力建立先後

想像三個朋友在不同城市，用通訊軟體聊天（對應三個行程 $p_1, p_2, p_3$）：

• 阿明在自己手機上『先打草稿（a）再送出（b）』——同一支手機，順序明確（HB1）。
• 阿明送出的訊息 $m_1$ 被阿華收到（c），所以『阿明送出 b』一定發生在『阿華收到 c』之前（HB2）。
• 阿華收到後又送了訊息 $m_2$ 給阿傑（d→f）。

把這些串起來：阿明送出 → 阿華收到 → 阿華再送 → 阿傑收到，於是阿明的 a『發生在之前』阿傑的 f（HB3 傳遞性）。

但如果阿傑自己在那段時間做了一件事 e，而這件事和阿明的 a 沒有任何訊息鏈相連，那我們就無法說誰先誰後——它們是並行的，就像兩個人各自在忙、互不知情。

實用超能力

潛在因果的兩個重要警告

為什麼叫『潛在』因果

用 happened-before 時要記住兩個重要警告：

警告一：它只捕捉『潛在』因果，不保證真有因果。

• 真因果例子：伺服器收到請求 → 送出回覆，回覆確實由請求引起。
• 假因果例子：某行程每 5 分鐘固定送一則訊息，剛好在收到某訊息之後送出——$\rightarrow$ 會把這兩者排序，但其實毫無因果。

警告二：有些真實的資料流它抓不到。

若 Smith 命令他的行程送訊息後『打電話』給 Jones，Jones 再命令她的行程送另一則訊息——第一則明明發生在第二則之前，但因為沒有網路訊息在兩行程間流動，這個模型抓不到這層關係。

flowchart LR
  a[阿明 打草稿 a] --> b[阿明 送出 b]
  b -->|訊息 m1| c[阿華 收到 c]
  c --> d[阿華 送出 d]
  d -->|訊息 m2| f[阿傑 收到 f]
  e[阿傑 獨立動作 e]

圖中 a 到 f 有因果鏈相連，但 e 和 a 並行。掌握這點，你就知道 happened-before 能排什麼、不能排什麼——這正是下一節邏輯時鐘要用數字捕捉的關係。

深度探秘

用一個計數器捕捉因果順序

邏輯時鐘是什麼

Lamport 發明了一個簡單機制，把 happened-before 順序用數字捕捉，叫邏輯時鐘 (logical clock)。

• 它是一個單調遞增的軟體計數器，數值與任何物理時鐘無關。
• 每個行程 $p_i$ 維護自己的邏輯時鐘 $L_i$，用它替事件蓋 Lamport 時戳。
• $L_i(e)$ 表示事件 $e$ 在 $p_i$ 的時戳；$L(e)$ 表示 $e$ 在其所在行程的時戳。

更新規則

為了捕捉 $\rightarrow$，行程依下列規則更新並在訊息中傳遞邏輯時鐘值：

• LC1：在 $p_i$ 發出每個事件之前，先遞增 $L_i$：$L_i := L_i + 1$。
• LC2 (a)：行程送訊息 $m$ 時，把 $L_i$ 的值 $t$ 夾帶在 $m$ 上。
• LC2 (b)：收到 $(m, t)$ 時，先計算 $L_j := \max(L_j, t)$，再套用 LC1 替 $receive(m)$ 事件標時。

（雖然這裡每次加 1，其實加任何正值都可以。）

關鍵性質與其限制

可由歸納法證明：

$$e \rightarrow e' \implies L(e) < L(e')$$

但反過來不成立！ 若 $L(e) < L(e')$，我們不能推斷 $e \rightarrow e'$。這是 Lamport 時鐘的根本限制（下一小章的向量時鐘就是為了補這個破綻）。

生活妙喻

接力賽的『至少第幾棒』號碼牌

號碼牌只增不減

把邏輯時鐘想成每個人手上的一張號碼牌，數字只增不減：

• 每做一件事前，先把自己號碼牌的數字加 1（LC1）。
• 送訊息給別人時，把『我現在的號碼』寫在信封上一起寄出（LC2a）。
• 收到信時，看看信封上的號碼，和自己的比，取較大者，然後再加 1（LC2b）。

這個『取較大者』的動作很關鍵：它確保『收信』這件事的號碼一定比『寄信』還大——因為因果關係要求果的數字大於因。

為什麼反推不成立

想像兩個互不通信的人，各自悶頭做事，號碼分別跑到 5 和 7。

• 你不能因為『7 比 5 大』就說『那個 7 的事件是被 5 引起的』——他們根本沒交換過任何訊息！
• 數字大只代表『在自己的世界裡走得比較遠』，不代表有因果關係。

這就是為什麼：有因果 → 號碼一定變大；但號碼大 → 不一定有因果。

實用超能力

全序版本與實際用途

做出全序

Lamport 時鐘有個小麻煩：不同行程的事件可能拿到相同的時戳。我們可以靠行程識別碼打破平手，造出全序 (total order)：

設 $e$ 在 $p_i$ 的本地時戳為 $T_i$、$e'$ 在 $p_j$ 為 $T_j$，定義全域邏輯時戳為 $(T_i, i)$ 與 $(T_j, j)$，並規定：

$$(T_i, i) < (T_j, j) \iff T_i < T_j,\ \text{或}\ (T_i = T_j\ \text{且}\ i < j)$$

這個順序沒有一般的物理意義（因為行程編號是任意的），但很有用——Lamport 就用它來排程行程進入臨界區 (critical section) 的順序。

範例追蹤

sequenceDiagram
  participant P1 as p1
  participant P2 as p2
  P1->>P1: 事件 a, L=1
  P1->>P2: 事件 b, L=2, 夾帶 2
  Note over P2: 收到時 max 0 與 2 等於 2, 再加一
  P2->>P2: 事件 c, L=3
  P2->>P2: 事件 d, L=4

各行程時鐘從 0 起算。注意可能出現 $L(b) = L(e)$（不同行程平手），這時就靠行程編號決勝。

重點回顧

1. 要排因果順序、又省空間 → 用 Lamport 時鐘（單一整數即可）。
2. 要明確打破平手 → 加上行程編號做全序。
3. 要從時戳反推因果或判斷並行 → Lamport 不夠，得用向量時鐘。

深度探秘

補上 Lamport 反推不成立的破綻

Lamport 的破綻

上一小章看到 Lamport 時鐘的限制：從 $L(e) < L(e')$ 推不出 $e \rightarrow e'$。也就是說，光看 Lamport 時戳，你無法判斷兩事件到底有沒有因果關係。

Mattern 與 Fidge 發明的向量時鐘 (vector clock) 就是為了克服這個缺點。

向量時鐘長什麼樣

對一個有 $N$ 個行程的系統，向量時鐘是一個長度為 $N$ 的整數陣列。每個行程 $p_i$ 維護自己的向量時鐘 $V_i$。更新規則：

• VC1：初始時 $V_i[j] = 0$，對所有 $j$。
• VC2：$p_i$ 替事件標時前，先做 $V_i[i] := V_i[i] + 1$（只動自己那一格）。
• VC3：$p_i$ 送的每則訊息都夾帶整個向量值 $t = V_i$。
• VC4：$p_i$ 收到夾帶時戳 $t$ 的訊息時，對每一格取最大值：$V_i[j] := \max(V_i[j], t[j])$，對所有 $j$。這種逐分量取最大叫 merge（合併）。

每一格的意義

對向量時鐘 $V_i$：

• $V_i[i]$ 是 $p_i$ 自己已標記的事件數。
• $V_i[j]$（$j \ne i$）是 $p_j$ 已發生、且可能影響過 $p_i$ 的事件數。

$p_j$ 也許已標記更多事件，但還沒有任何訊息把這些資訊流到 $p_i$，所以 $p_i$ 還不知道。

生活妙喻

每個人手上的『見聞記分板』

一塊記著每個人進度的板子

把向量時鐘想成每個人手上一塊記分板，上面有 $N$ 格，每格寫『我所知道的，某某人到目前做了幾件事』。

以三人系統為例，阿明的記分板長這樣：[阿明, 阿華, 阿傑]。

• 阿明自己做一件事 → 只把自己那格加 1（VC2），例如 [2, 0, 0]。
• 阿明寄信給阿華 → 把整塊記分板拍照附在信裡寄出（VC3）。
• 阿華收到信 → 把信裡阿明的記分板和自己的逐格比對、各取較大者（VC4 merge），於是阿華不只更新對阿明的認知，連阿明所知道的阿傑進度也一併吸收了。

妙處在於：記分板上『阿傑那格』的數字，代表的是『我所聽聞到的阿傑進度』，而不是阿傑此刻真正的進度——消息要透過訊息一棒棒傳過來，我才會知道。

實用超能力

親手追一遍三行程範例

範例：三個行程的向量時戳

沿用前面三行程的例子，初始都是 [0,0,0]：

怎麼讀這些數字

flowchart LR
  a[a 等於 1,0,0] --> b[b 等於 2,0,0]
  b -->|m1| c[c 等於 2,1,0]
  c --> d[d 等於 2,2,0]
  d -->|m2| f[f 等於 2,2,2]
  e[e 等於 0,0,1]

• $f = (2,2,2)$ 說明 $p_3$ 在事件 f 時，已透過訊息鏈間接知道 $p_1$ 的 2 個、$p_2$ 的 2 個事件——這正反映 $a \rightarrow f$。
• $e = (0,0,1)$ 的 p1、p2 格都是 0，代表 e 發生時 $p_3$ 對 $p_1, p_2$ 一無所知——它和 a 是並行的。

重點

1. 只動自己那格（標時前），收訊息才 merge 其他格。
2. 每格是『我所知道的對方進度』，靠訊息傳遞。
3. 這套記法讓我們能直接比較時戳判斷因果——下一節登場。

深度探秘

比較規則：小於等於就是有因果

怎麼比較兩個向量時戳

向量時戳的比較是逐分量的：

• $V = V'$：每一格都相等，即 $V[j] = V'[j]$ 對所有 $j$。
• $V \le V'$：每一格都小於等於，即 $V[j] \le V'[j]$ 對所有 $j$。
• $V < V'$：$V \le V'$ 且 至少有一格嚴格小於（$V \ne V'$）。

關鍵性質（雙向都成立！）

設 $V(e)$ 為事件 $e$ 所在行程賦予的向量時戳。可證明：

$$e \rightarrow e' \iff V(e) < V(e')$$

注意這是雙向 (iff)！這正是向量時鐘勝過 Lamport 時鐘之處：Lamport 只有單向（有因果則時戳變大），向量時鐘則能從時戳直接反推因果。

怎麼判斷並行

兩事件 $e$、$e'$ 並行的條件是：

$$\text{既不 } V(e) \le V(e')\ \text{也不 } V(e') \le V(e)$$

也就是兩個向量互不小於等於——你有一格比我大、我也有一格比你大，誰也不包含誰。

生活妙喻

比兩張記分板誰『樣樣不落後』

樣樣不落後 = 有因果

回到記分板比喻。要判斷『事件 e 是不是發生在 e' 之前』，就把兩張記分板攤開逐格比：

• 如果 e' 的記分板每一格都 ≥ e 的記分板，且至少有一格更大——代表 e' 知道的見聞完整涵蓋了 e 知道的，還更多。這只可能是因為 e 的資訊順著訊息鏈流到了 e'，所以 e 發生在 e' 之前。

互有勝負 = 並行

• 如果比下來『你有一格贏我、我也有一格贏你』——代表雙方各自知道一些對方不知道的事，誰也沒涵蓋誰。這就表示他們之間沒有訊息鏈相連，是並行的。

用記分板的話說：誰的見聞完整包住另一個，誰就在後面；要是互有獨家消息，那就是各做各的、並行。

對照範例

• $V(a) = (1,0,0)$、$V(f) = (2,2,2)$：f 每格都 ≥ a 且更大，所以 $a \rightarrow f$。✅
• $V(c) = (2,1,0)$、$V(e) = (0,0,1)$：c 的第一格贏 e，e 的第三格贏 c，互有勝負 → $c \parallel e$（並行）。

實用超能力

代價：空間與訊息負載正比於 N

天下沒有白吃的午餐

向量時鐘能精準判斷因果與並行，但有代價：

• 它佔用的儲存空間與訊息負載都正比於 $N$（行程數）。系統越大，每則訊息要背的向量越長。
• Charron-Bost 證明：如果想單憑時戳判斷兩事件是否並行，這個維度 $N$ 是無法避免的——這是理論下限，不是實作偷懶。

怎麼省一點

• 存在一些技術可儲存與傳輸較少的資料，代價是重建完整向量時需要額外運算（Raynal 與 Singhal 有整理）。
• 還有矩陣時鐘 (matrix clock) 的概念：行程不只記自己的向量時間，還記下對其他行程向量時間的估計。

怎麼選工具

flowchart TD
  A{我需要什麼} --> B[只要排個順序又省空間]
  A --> C[要能反推因果或判斷並行]
  B --> D[用 Lamport 時鐘, 單一整數]
  C --> E[用向量時鐘, 長度 N 陣列]
  E --> F[在意成本則用壓縮技術或矩陣時鐘]

選擇關鍵：你需不需要『從時戳反推因果或判斷並行』？需要就付出 $N$ 的代價用向量時鐘。

深度探秘

為什麼觀察全域狀態這麼難

動機：四個需要看全貌的問題

很多分散式問題都需要知道『整個系統某瞬間的樣子』：

• 分散式垃圾回收：物件若全系統都沒有任何參照就是垃圾，可回收記憶體。注意——參照可能藏在傳輸中的訊息裡，所以必須連通道狀態一起看。
• 分散式死結偵測：一群行程在『等待』關係圖中形成環，誰也動不了。
• 分散式終止偵測：不能只看每個行程是否停下；一個 passive（被動）行程可能因為收到一則『路上的訊息』又變回 active。
• 分散式除錯：例如要求各行程變數 $x_i$ 彼此差距 $|x_i - x_j| \le \delta$，這要在『同一時間』的值上評估。

困難的根源

核心難題就是缺乏全域時間。若所有時鐘完美同步，我們就能約好某一刻讓每個行程記錄自己的狀態，拼出真正的全域狀態。但做不到完美同步，這條路走不通。

所以問題變成：能不能把不同真實時刻記錄的本地狀態，拼成一個有意義的全域狀態？ 答案是『有條件的可以』。

生活妙喻

拼貼一張『全班合照』

沒辦法讓大家同時按快門

想像你想拍一張全班合照，但同學散在世界各地、各有各的相機，沒辦法喊『一、二、三』同時按快門（沒有全域時間）。

你只能各自在不同時刻拍自己的照片，再拼成一張合照。問題是：這張拼出來的合照，可能呈現一個從未真實發生過的瞬間。

什麼叫『不一致』的合照

舉個荒謬的例子：

• 阿華的照片裡『手上拿著一封信』（已收到訊息）。
• 但阿明的照片裡『還沒把那封信寄出去』（尚未送出訊息）。

這就是有果無因——信都還沒寄，怎麼會有人收到？這種拼貼是不一致割面 (inconsistent cut)。真實的執行從來沒有處於這種狀態。

反過來，如果合照裡『阿明已寄出、阿華還沒收到』，那完全合理——信在路上嘛！這就是一致割面 (consistent cut)。

實用超能力

一致割面的形式定義與線性化

割面與一致的定義

把每個行程的歷史取一段前綴，合起來就是一個割面 (cut)，其『最後事件』構成割面的邊界 (frontier)。

一致割面 (consistent cut) 的條件：對割面內的每個事件 $e$，所有 $e' \rightarrow e$ 的事件也都在割面內。

$$\text{對所有事件 } e \in C,\quad f \rightarrow e \implies f \in C$$

白話：把任何一個事件收進來，就得把它的所有『前因』一起收進來。

系統的演進

flowchart LR
  S0[一致全域狀態 S0] --> S1[S1]
  S1 --> S2[S2]
  S2 --> S3[後續一致狀態]

• 系統可看成一連串一致全域狀態之間的轉移，每次轉移恰好發生一個事件。
• run（執行）：所有事件的一個全序，且與各本地歷史順序一致。
• linearization / consistent run（線性化）：與 happened-before 關係一致的 run。

關鍵結論：並非所有 run 都經過一致全域狀態，但所有 linearization 都只經過一致全域狀態。 若存在一個 linearization 先經過 $S$ 再到 $S'$，就說 $S'$ 從 $S$ 可達 (reachable)。

這套『一致割面』的觀念，就是下一節 Chandy-Lamport 快照演算法要捕捉的目標。

深度探秘

用 marker 訊息拍下一致快照

目標與假設

Chandy 與 Lamport 的快照 (snapshot) 演算法目標是：記錄一組行程與通道狀態，即使這些狀態不曾在同一時刻發生，組合起來仍是一致的全域狀態。

演算法的假設：

• 通道與行程都不失效，訊息可靠、恰好送達一次。
• 通道是單向且提供 FIFO 順序傳遞。
• 行程與通道的圖是強連通的（任兩行程間有路徑）。
• 任何行程可在任何時刻發起快照，且系統不必停下，可繼續正常收送訊息。

核心點子

每個行程記錄自己的狀態，並對每條入向通道記錄一組訊息——具體是『在我記錄狀態之後、但在送方記錄它自己狀態之前到達的訊息』。這樣就能用『傳輸中但尚未收到的訊息』來補上不同時刻記錄之間的差異。

marker 的雙重角色

演算法靠特殊的 marker（標記）訊息運作，它有兩個角色：

1. 提示接收者存自己的狀態（如果還沒存的話）。
2. 界定哪些訊息該算進通道狀態。

生活妙喻

派『分隔板』走過每條輸送帶

超市結帳輸送帶上的分隔板

想像幾家工廠用單向輸送帶互相運送貨物（單向 FIFO 通道）。某廠想拍下『此刻全網的庫存與在途貨物』快照，但不能讓輸送帶停下。

做法是放一塊分隔板（marker）：

• 發起者先盤點自己的庫存（記錄狀態），然後在每條出向輸送帶上放一塊分隔板，之後才繼續送正常貨物。
• 第一次看到分隔板的工廠：立刻盤點自己庫存（這是它第一次收到 marker），把『送來這塊分隔板的那條帶子』的通道狀態記成空集合，並開始記錄其他輸送帶上後續到來的貨物；接著也往自己每條出向帶子放分隔板。
• 已經盤點過、又在別條帶子收到分隔板的工廠：把『從我盤點完到這塊分隔板之間，這條帶子上收到的貨物』記成該通道的狀態。

分隔板就像一條『時間分界線』：它前面的貨物算『盤點前』，後面的算『盤點後』。因為帶子是 FIFO，分隔板不會被後送的貨物超車，分界乾淨俐落。

實用超能力

兩條規則、widget 範例與終止性

兩條規則

flowchart TD
  A[行程收到 marker] --> B{我存過狀態了嗎}
  B -->|還沒| C[記錄自己狀態, 該通道狀態記為空, 開始記錄其他入向通道]
  C --> D[依送出規則往每條出向通道送 marker]
  B -->|存過了| E[把這條通道狀態記為自存狀態後在此收到的訊息集合]

• marker 接收規則：見上圖。發起者就當作自己從一條不存在的通道收到 marker，據此啟動。
• marker 送出規則：行程記錄狀態後、送任何其他訊息前，往每條出向通道送一個 marker。

widget 範例（兩行程 p1、p2）

• 初始：$p_1$ <$1000, 0 widgets>、$p_2$ <$50, 2000 widgets>。
• $p_1$ 在 $S_0$ 記錄狀態 <$1000, 0>，送出 marker，再送應用訊息（Order 10, $100）。
• $p_2$ 收到 marker 前先沿通道送出五個 widget；隨後 $p_2$ 收到五個 widget、再收到 marker，記錄狀態 <$50, 1995>、通道 $c_2$ 狀態為空，並送出自己的 marker。
• $p_1$ 收到 $p_2$ 的 marker，把通道 $c_1$ 狀態記成『存狀態後收到的那一則：五個 widget』。

最終記錄狀態：$p_1$ <$1000, 0>；$p_2$ <$50, 1995>；$c_1$ <五個 widget>；$c_2$ <空>。注意這個狀態和系統實際經過的任何全域狀態都不同，但它是一致的！

終止性

若每個收到 marker 的行程都在有限時間內記錄狀態並沿每條出向通道送出 marker，加上圖是強連通，則所有行程都會在發起者記錄狀態後的有限時間內完成記錄。

深度探秘

穩定述詞、安全性與存活性

全域狀態述詞

偵測死結、終止等情況，等於在評估一個全域狀態述詞 (global state predicate)——一個把全域狀態映射到 {True, False} 的函式。

穩定 vs 非穩定

• 穩定述詞 (stable predicate)：一旦系統進入使述詞為 True 的狀態，之後所有可達狀態都維持 True。例如『物件是垃圾』『系統死結』『系統終止』——這些一旦成立就不會反悔。
• 非穩定述詞 (non-stable predicate)：可能一下成立、一下又不成立。例如『各變數差距在界限內』——即使某刻滿足，也可能下一刻又被打破。監控與除錯常關心這類述詞。

安全性與存活性

針對全域狀態述詞，還有兩個重要概念。設 $S_0$ 為系統初始狀態：

• 安全性 (safety)：對一個不希望發生的性質 $\alpha$（如死結），安全性斷言 $\alpha$ 對所有從 $S_0$ 可達的狀態都為 False——也就是壞事永不發生。
• 存活性 (liveness)：對一個希望達成的性質 $\beta$（如終止），存活性斷言對任何從 $S_0$ 出發的 linearization，總會有某個可達狀態使 $\beta$ 為 True——也就是好事終究會發生。

生活妙喻

覆水難收 vs 忽明忽暗的燈

兩種述詞像兩種開關

• 穩定述詞像『覆水難收』：水一旦潑出去，之後永遠是潑出去的狀態，不會自己跳回杯子裡。死結也是——一旦卡死，沒有外力就永遠卡死。所以你只要某一刻抓到它成立，就能放心斷定『它真的發生了』。
• 非穩定述詞像『忽明忽暗的閃爍燈』：你某一瞬間看到燈亮，不代表它一直亮；你也可能剛好錯過它亮的那一刻。所以單看一張快照，很難說它『到底有沒有亮過』。

安全與存活的生活版

• 安全性＝『壞事永遠別發生』。例如工廠的安全規則：閥門絕不可在某情況下全開（不希望的性質永不成立）。
• 存活性＝『好事終究會發生』。例如你按了電梯，電梯遲早會來（想要的性質終會達成）。

一句口訣：安全性說『不好的永遠不會發生』，存活性說『好的早晚會發生』。

實用超能力

possibly 與 definitely 的分散式除錯

為什麼需要 possibly 與 definitely

除錯非穩定述詞（如『$|x_i - x_j| \le \delta$ 曾被違反嗎？』）時，單一快照不夠。Marzullo 與 Neiger 用一個**集中式 monitor（監視器）**收集各行程狀態，組成所有一致全域狀態，並定義兩種判斷：

• possibly $\phi$（可能）：存在 $H$ 的某個 linearization 經過某個一致全域狀態 $S$，使 $\phi(S)$ 為 True。
• definitely $\phi$（必定）：對 $H$ 的所有 linearization $L$，都存在 $L$ 經過的某個一致全域狀態使 $\phi$ 為 True。

關鍵邏輯關係

flowchart TD
  A[definitely φ 必定發生] --> B[possibly φ 可能發生]
  B -.推不回去.-> A

• 從 definitely φ 可以推出 possibly φ。
• 但從 possibly φ 不能推出 definitely φ。
• 只有當 $\phi$ 對所有一致全域狀態都為 False，才能說『並非 possibly $\phi$』。

與快照演算法的關係

用 Chandy-Lamport 快照得到狀態 $S_{snap}$：

• 若 $S_{snap}$ 使 $\phi$ 為 True，可斷言 possibly φ。
• 對穩定述詞特別好用：因為記錄到的狀態 $S_{snap}$ 介於 $S_{init}$ 與 $S_{final}$ 之間且可達，若穩定述詞在 $S_{snap}$ 為 True，則它在 $S_{final}$ 也為 True；若在 $S_{snap}$ 為 False，則在 $S_{init}$ 也為 False。