深度探秘

一群電腦如何在沒有老大時合作

核心問題

想像一艘太空船由好幾台電腦一起控制。任務要『繼續 proceed』還是『中止 abort』，這些電腦必須取得一致，否則一台推進、一台煞車，結果不堪設想。

這就是本章的主題：協調（coordination） 與 共識（agreement）。

協調：一群程序在沒有固定『主從關係』的情況下，仍要正確地合作使用共享資源、或對某些值達成一致。

為什麼不乾脆指定一台當『老大（master）』就好？因為老大會壞。一旦它當機，整個系統就跟著癱瘓，這叫單點失效（single point of failure）。我們希望系統就算有零件壞掉也能繼續運作，所以要避免固定的老大。

同步 vs 非同步

本章一個關鍵分野：系統是同步（synchronous） 還是非同步（asynchronous）？

生活妙喻

沒有班長的分組報告

比喻：四人小組做報告，但沒有組長

四個同學要合作交一份報告，卻沒有指定組長。

• 他們得輪流改同一份 Google 文件，不能同時亂改（這就是後面要講的互斥）。
• 如果有人突然不讀訊息了，大家得選一個人來統籌（這是選舉）。
• 公告要讓每個人都看到、而且看到的順序一致（這是群組通訊的排序）。
• 最後對『要不要熬夜趕工』要全體一致（這是共識）。

同步 vs 非同步的比喻

• 同步像在同一間教室開會：你喊一句，最慢三秒內一定聽得到回應，沒回應就是這人睡著了（可用 timeout 判斷）。
• 非同步像用 email 聯絡：對方可能五分鐘回、也可能五天才回。沒收到回信，你永遠分不清他是已讀不回、還是手機壞了。

實用超能力

面對失效，循序漸進

設計演算法時怎麼一步步面對失效

本章的鋪陳很有教學味道，從『不能容忍任何失效』慢慢進階到『容忍任意失效』：

1. 先假設不會有任何失效  → 把基本想法講清楚
2. 容忍善意的失效（crash）→ 程序只會乾脆地停掉
3. 容忍任意失效（Byzantine）→ 程序可能亂送、說謊

本章地圖

flowchart TD
  A[協調與共識] --> B[分散式互斥 排隊用資源]
  A --> C[選舉 選出新負責人]
  A --> D[群組通訊 可靠與有序群播]
  A --> E[共識 對一個值取得一致]
  E --> F[震撼結論 非同步系統無法保證共識]

你會學到的震撼結論

本章會遇到分散式系統理論中最有名的結果之一：即使在很溫和的失效條件下，非同步系統也無法保證一群程序能對一個共享值達成一致。這就是後面要講的 FLP 不可能定理。

深度探秘

誰壞了？我們其實常常不知道

先講清楚我們假設了什麼

本章為了簡化，先做幾個假設：

• 每對程序之間都有可靠通道（reliable channel）：底層網路可能掉封包，但通訊協定會重送、修正，最終一定把訊息送到對方的輸入緩衝區。
• 程序只會以 crash 方式失效（乾脆地停掉，不會亂送東西）—— 除非另外說明。一個從頭到尾沒出錯的程序叫正確程序（correct process）。

網路分割（network partition）

有時某個路由器壞了，四個程序被切成兩半：同一半內可以通訊，但兩半之間不行。這就是網路分割。連通性還可能很詭異：

• 不對稱：p 能送到 q，但 q 送不回 p。
• 不遞移：p 能到 q、q 能到 r，但 p 直接到不了 r。

失效偵測器（failure detector）

要設計能撐過 crash 的演算法，第一步是判斷某程序是不是掛了。負責回答這個問題的服務就叫失效偵測器，通常是跑在每台機器本機的一個物件（local failure detector）。

生活妙喻

室友到底是出門了還是在睡覺

比喻：判斷室友在不在

你想知道室友在不在房間，只能靠『有沒有聽到動靜』。

• 不可靠失效偵測器（unreliable） 只會給你兩種猜測：
  • 未懷疑 Unsuspected：『剛剛還聽到他講話』→ 大概在，但他也可能話一說完就出門了。
  • 懷疑 Suspected：『好久沒聲音了』→ 可能出門，但也可能只是在睡覺或戴耳機。

這兩個答案都只是提示（hint），不保證準！懷疑可能搞錯（其實人在），也可能漏掉（其實人不在卻沒被懷疑）。

• 可靠失效偵測器（reliable） 比較強：它若說 Failed，就是真的確定室友離開了（而且 crash 的程序一旦死就不會復活）。但它只在同步系統（你住的是隔音超好、規律到秒的宿舍）才做得出來。

心跳偵測

常見實作：每個程序每隔 T 秒對大家喊一聲『我還在 p is here』。若程序 q 在 $T + D$ 秒內（D 是估計的最大傳輸時間）沒收到 p 的喊聲，就回報 p 被 Suspected；之後若又收到，就改回 OK。

實用超能力

timeout 要設多大才剛好

timeout 的兩難

心跳機制的關鍵是 $T + D$ 這個 timeout 要設多大：

實務解法：自適應 timeout

讓 timeout 跟著觀察到的網路延遲動態調整。如果某次心跳花了 20 秒才到（原本預期最多 10 秒），就把那個程序的 timeout 往上調。偵測器仍然不可靠、答案仍只是提示，但準確的機率提高了。

flowchart TD
  A[每隔 T 秒收心跳] --> B{在 timeout 內收到了嗎}
  B -- 有 --> C[回報 Unsuspected 並依延遲調整 timeout]
  B -- 沒有 --> D[回報 Suspected]
  D --> E{之後又收到心跳}
  E -- 是 --> C

為什麼還是有用

就算不準，失效偵測器幫我們把『失效』這件事概念化。任何要對抗失效的系統都得偵測失效——即使偵測得不完美。後面會看到，連『不可靠但具備某些良好性質』的偵測器，都能幫我們解決共識問題。

深度探秘

臨界區問題搬到網路上

什麼是分散式互斥

當一群程序共用某個資源時，常常需要互斥（mutual exclusion）：同一時間只准一個程序在使用，以免互相干擾、破壞一致性。這就是作業系統裡熟悉的臨界區問題（critical section problem）。

但在分散式系統裡，我們不能用共享變數，也沒有單一核心能幫我們上鎖。唯一能用的就是——互相傳訊息。

使用臨界區的流程

應用層的協定長這樣：

enter()            // 進入臨界區，必要時阻塞等待
resourceAccesses() // 在臨界區內存取共享資源
exit()             // 離開臨界區，其他程序現在可以進來了

三條必須遵守的規則

• ME1（安全性 safety）：任何時刻最多一個程序在臨界區內。
• ME2（活躍性 liveness）：進入與離開臨界區的請求終究會成功（不會 deadlock，也不會 starvation）。
• ME3（排序 ordering）：若一個進入請求 happened-before 另一個，則授予進入的順序也要照這個順序。

生活妙喻

公司只有一間會議室

比喻：搶用唯一的會議室

整層樓只有一間會議室（臨界區），大家得協調誰能進去開會。

• ME1 安全性：絕不能兩組人同時擠進去開會（會吵架）。
• ME2 活躍性：每個想開會的人最後一定排得到——不會卡死（deadlock：兩組人互相等對方先讓），也不會被無限晾在一邊（starvation：永遠輪不到）。
• ME3 排序：如果小明『先』登記，而且這個『先』是有因果關係的（小明登記後還傳訊息叫小華也去登記），那系統應該讓小明先用。

為什麼不能用時間排序？

你可能想：那就照『登記時間』排不就好了？問題是分散式系統沒有全域時鐘，每台電腦的錶都不一樣準，無法可靠比較『誰真的先』。所以 ME3 改用第 14 章的 happened-before（因果先後）關係來排序。

實用超能力

用三把尺評估演算法

怎麼比較不同的互斥演算法

後面會看到好幾種互斥演算法，我們用三個指標來評估它們：

同步延遲為什麼重要

同步延遲（synchronization delay） 決定了整個系統的吞吐量：一個人剛離開、下一個人能多快進去。延遲越短，大家輪流用資源的速度就越快。

flowchart LR
  A[程序1 離開臨界區] -->|同步延遲| B[程序2 進入臨界區]
  B -->|同步延遲| C[程序3 進入臨界區]

我們假設用戶端是『乖寶寶』：在臨界區內只待有限的時間，不會賴著不走。

深度探秘

最直覺的兩種互斥

中央伺服器演算法

最簡單的方法：找一台伺服器來發token（令牌）。

• 想進臨界區的程序送 request 給伺服器，等回覆。
• 若 token 沒人拿，伺服器立刻回覆，等於把 token 給它。
• 若 token 在別人手上，伺服器不回覆，把請求排進佇列。
• 程序離開臨界區時送 release 把 token 還回去；伺服器再從佇列挑最舊的請求發出去。

效能：進入要 2 則訊息（request + grant），離開要 1 則（release）。同步延遲是一個來回（round-trip）：release 到伺服器、再 grant 給下一位。缺點是伺服器是瓶頸也是單點失效，而且不滿足 ME3。

環狀演算法（ring-based）

把 N 個程序排成邏輯環，每個只需要能送訊息給環上下一個鄰居。token 沿著環單向（例如順時針）一直傳。

• 收到 token 但不想進臨界區 → 立刻轉給鄰居。
• 想進 → 收到後留著，進臨界區；離開時把 token 傳給鄰居。

生活妙喻

圖書館櫃台 vs 傳遞發言棒

中央伺服器＝圖書館借閱櫃台

只有一本熱門書（token）。你去櫃台借（request），有書就借你（grant），沒書館員把你登記排隊。還書（release）後，館員叫排最久的下一位來拿。

• 優點：超直覺。
• 缺點：櫃台大排長龍（瓶頸），館員請假整個借閱系統就停擺（單點失效）。

環狀＝營火晚會傳發言棒

大家圍成一圈，發言棒順時針一直傳。

• 拿到棒子但沒話說 → 馬上傳給下一個人。
• 想發言 → 拿到就留著講，講完再傳出去。

flowchart LR
  P1[程序1] --> P2[程序2]
  P2 --> P3[程序3]
  P3 --> P4[程序4]
  P4 --> P1

有趣的代價：就算沒人想發言，棒子還是得一直繞圈傳，持續消耗頻寬（網路一直有訊息在跑）。

實用超能力

兩種方法的延遲帳本

環狀法的延遲算盤

環狀演算法的延遲很看運氣：

• 一個程序想進臨界區，要等的訊息數介於 0（剛好 token 在手）到 N（剛好把 token 傳出去）之間。
• 離開臨界區只要 1 則訊息。
• 同步延遲：1 到 N 個訊息傳遞時間之間。

兩種方法快速對照

容錯的殘酷現實

這兩種（以及後面要講的）演算法原樣都撐不住失效：

• 通道不可靠（會掉訊息）→ 全部都壞。
• 環狀法任一程序當機，環就斷了，token 傳不下去。
• 中央伺服器至少還能容忍『沒拿也沒請求 token 的用戶端』當掉。

深度探秘

用群播與時戳達成去中心化互斥

Ricart 與 Agrawala 演算法

這個演算法不需要任何伺服器或環，N 個對等程序靠群播（multicast）+ Lamport 時戳互斥。基本想法：想進臨界區的程序群播一個 request，只有當其他所有程序都回覆後才能進去。

每個程序有三種狀態：RELEASED（在外面）、WANTED（想進）、HELD（在裡面）。收到別人的 request 時的規則：

收到來自 pi 的 request <Ti, pi>：
  if (state = HELD) 或 (state = WANTED 且 自己的(T, pj) < (Ti, pi))
  then  把 pi 的 request 排隊，先不回
  else  立刻回覆 pi

關鍵：用 (時戳, 程序編號) 做全序比較。時戳小的先贏；時戳一樣就比程序編號。誰的請求時戳最小，就最快收齊回覆、最先進入。

效能：取得進入要 $2(N-1)$ 則訊息（群播 request + 收 N-1 個 reply），有硬體群播則只要 N 則。優點是同步延遲只要一個訊息傳遞時間（比前兩種的來回都短）。

生活妙喻

群組徵求同意 vs 拉攏關鍵選票

Ricart-Agrawala＝群組裡徵求大家同意

你想用共享的會議室，於是在群組喊：『我 10:41 想用會議室！』（時戳 41）。

• 不想用的人立刻回你『OK』。
• 也想用、而且比你更早登記（時戳更小）的人，會先不回你，等他用完才回。
• 等所有人都回 OK 了，你才進去。

同時兩個人喊？比時戳，早的先進；時戳一樣就比學號（程序編號）。

Maekawa＝只需拉攏關鍵選票

Maekawa 的洞見很妙：你不必徵求所有人同意，只要徵求一個『投票集合 $V_i$』裡的人同意就好。訣竅是任兩個程序的投票集合一定有交集，交集裡的人一次只投給一個候選人，就能保證 ME1 安全性。

flowchart TD
  A[程序i 想進臨界區] --> B[只向投票集合 Vi 的成員要票]
  B --> C[集合交集的成員一次只投一人]
  C --> D[收齊 K 票才進入 保證最多一人]

實用超能力

Maekawa 的省訊息與死結風險

Maekawa 的數學巧思

每個程序有自己的投票集合 $V_i$，設計時要求：

• $V_i \cap V_j \neq \varnothing$：任兩個投票集合至少有一個共同成員（保證安全）。
• $|V_i| = K$：每個集合大小一樣（公平）。

最佳解大約是 $K \approx \sqrt{N}$，做法是把程序排成 $\sqrt{N} \times \sqrt{N}$ 的矩陣，$V_i$ 取『該程序所在的整列加整欄』。

頻寬：進入 $2\sqrt{N}$、離開 $\sqrt{N}$，合計 $3\sqrt{N}$，當 $N > 4$ 時優於 Ricart-Agrawala 的 $2(N-1)$。

但是會死結！

Maekawa 原始版會死結。經典反例：三個程序 $V_1={p_1,p_2}$、$V_2={p_2,p_3}$、$V_3={p_3,p_1}$。若三人同時請求：

p1 投給自己、卡住 p3
p2 投給自己、卡住 p1
p3 投給自己、卡住 p2
→ 每人只收到 1 票（要 2 票），全部卡死！

Sanders 的改良版讓程序依 happened-before 順序排隊未處理的請求，就能變得無死結，還順便滿足 ME3。代價：同步延遲變成一個來回（比 Ricart-Agrawala 差）。

深度探秘

選出唯一的負責人

什麼是選舉演算法

選舉演算法（election algorithm） 的目的：從一群程序中選出唯一一個來扮演特殊角色（例如取代當機的協調者、時間伺服器或鎖伺服器）。

關鍵需求：所有程序都要對選誰達成一致，而且就算多個程序同時發起選舉，最後也只能選出同一個。

慣例：選識別碼（identifier）最大的那個。識別碼可以是任何唯一且可全序排列的值。聰明的技巧——若想選『負載最低』的，就用 $\langle 1/load, i \rangle$ 當識別碼（負載越低、$1/load$ 越大），i 是程序編號用來打破平手。

兩條需求

每個程序有變數 electedᵢ 記住選出的識別碼，剛參與時設成特殊值 ⊥（未定）。

• E1（安全性）：參與中的程序，其 electedᵢ 不是 ⊥ 就是 P，其中 P 是這輪結束時沒當機、識別碼最大的程序。
• E2（活躍性）：所有程序都參與，最終要嘛設好 electedᵢ（不是 ⊥），要嘛當機。

生活妙喻

圍圈傳紙條選班長

比喻：圍成一圈傳紙條比學號

一群同學圍成圈（邏輯環），要選『學號最大』的當班長，但每個人只認得右邊鄰居，不知道全班學號。

Chang-Roberts 環狀選舉這樣玩：

1. 任何人都能發起：把自己的學號寫進紙條，傳給右邊鄰居，並標記自己『參與中』。
2. 收到紙條，比較紙上學號和自己的：
   • 紙上比我大 → 原封不動傳下去。
   • 紙上比我小且我還沒參與 → 把學號換成我的，再傳；但如果我已經參與了，就不傳（消滅重複）。
3. 若收到的紙條上學號正是自己 → 代表我最大，我就是班長！我把自己標回『非參與』，發出 elected 訊息宣布結果繞圈傳。

flowchart LR
  A[發起者寫上自己學號] --> B{收到的學號比我大}
  B -- 是 --> C[原樣轉發]
  B -- 否 --> D{我已參與了嗎}
  D -- 否 --> E[換成我的學號轉發]
  D -- 是 --> F[丟棄不轉發]

實用超能力

為什麼正確，效能多少

為什麼一定選出唯一贏家（E1）

所有識別碼都會被比較，因為一個程序必須收到自己的識別碼繞一圈回來才會宣布當選。對任兩個程序來說，大的不會幫小的傳，所以不可能兩個人都收到自己的識別碼回來 → 贏家唯一。

participant 標記的妙用

為什麼要有『參與/非參與』狀態？因為兩個人可能同時發起選舉，產生重複的選舉訊息。participant 標記讓這些重複訊息盡早被消滅，而且總在『贏家結果公告之前』就清掉。

效能

最壞情況：發起者的逆時針鄰居識別碼最高。

• 訊息傳到該鄰居：$N-1$ 則。
• 它的識別碼再繞一整圈確認最大：再 $N$ 則。
• elected 訊息繞一圈公告：再 $N$ 則。
• 合計約 $3N-1$ 則訊息，turnaround time 也是 $3N-1$（這些是接連送出的）。

限制：環狀選舉不容忍任何失效，所以實務價值有限——但有可靠失效偵測器時，原則上可在程序當機後重組環。

深度探秘

識別碼大的直接霸凌上位

惡霸演算法的前提

與環狀選舉不同，惡霸演算法（bully algorithm） 允許程序在選舉過程中當機，但假設：

• 系統是同步的（用 timeout 偵測失效）。
• 每個程序都知道哪些程序的識別碼比自己大，而且能直接跟它們通訊。

因為是同步系統，可以做出可靠失效偵測器：設最大傳輸延遲 $T_{trans}$、最大處理延遲 $T_{process}$，則 $T = 2T_{trans} + T_{process}$ 是『送出訊息到收到回應』的上限。超過 T 沒回應，就判定對方失效。

三種訊息

• election：宣布發起選舉。
• answer：回應 election，表示『我還活著、輪不到你』。
• coordinator：宣布當選者（新協調者）的身分。

流程

• 知道自己識別碼最高的程序，可直接送 coordinator 給所有比它小的程序，自封協調者。
• 識別碼較低的程序發現協調者失效時，送 election 給所有比自己大的程序，等 answer。
  • T 時間內沒人回 answer → 我最大，送 coordinator 給所有比我小的，自封協調者。
  • 有人回 answer → 等對方送 coordinator；若再等不到，重新發起選舉。

生活妙喻

誰塊頭大誰當老大

比喻：辦公室裡按年資搶主管

主管（協調者）離職了，大家要推新主管，規則是『年資最深的當』（識別碼最大）。每個人都知道誰比自己資深。

• 你發現主管不見了，就去問所有比你資深的人：『要選新主管囉？』（election）
• 比你資深的人回你：『我還在，這輪沒你的份。』（answer）然後他自己也去問更資深的人。
• 如果你問了一圈沒人回應（都離職或不在），代表你最資深，你就直接昭告天下我是新主管（coordinator）。

flowchart TD
  A[發現協調者失效] --> B[送 election 給所有更大者]
  B --> C{T 內收到 answer 嗎}
  C -- 否 --> D[我最大 送 coordinator 自封協調者]
  C -- 是 --> E[等更大者送 coordinator]
  E --> F{等到了嗎}
  F -- 否 --> B

為什麼叫『惡霸』

當一個壞掉的程序被重啟取代，新上來的若識別碼最高，就算現任協調者好好的，它也會跳出來說『我最大，我當！』直接搶位——像個霸道的新人，所以叫惡霸。

實用超能力

效能與會出錯的地方

效能

• 最佳情況：第二高識別碼的程序最先發現協調者失效，它直接自封並送 coordinator，turnaround 只要 1 個訊息。
• 最壞情況：識別碼最低的程序最先發現失效，於是 $N-1$ 個程序都發起選舉，各自送訊息給比自己大的，總共約 $O(N^2)$ 個訊息。

它什麼時候會出錯（破壞 E1）

惡霸演算法不總是滿足安全性 E1：

• 當機程序被同識別碼的新程序取代：取代者剛上線決定自己最大，另一個偵測到原程序當機的程序也決定自己最大 → 兩個都自封協調者，而且因為訊息沒有順序保證，不同接收者可能得到不同結論。
• timeout 假設不準（失效偵測器其實不可靠）：若某程序只是『跑很慢』而非真當機（系統其實不夠同步），它和別人可能同時發 coordinator，造成不同程序的 electedᵢ 不一致，E1 被打破。

重點

惡霸演算法滿足活躍性 E2（靠可靠訊息傳遞），在無取代且 timeout 準確時滿足 E1；但它的正確性高度依賴系統真的同步。

深度探秘

把訊息送給一整群人

群播與 deliver vs receive

群播（multicast） 是把一則訊息 multicast(g, m) 送給群組 g 的所有成員。收方用 deliver(m) 取得訊息。

注意用 deliver（交付） 而非 receive（接收）：訊息到達節點不代表立刻交給應用層，有時要先在佇列裡等排序條件滿足才交付。

基本群播 B-multicast

最直接的實作：對群組每個成員用可靠的一對一 send。

B-multicast(g, m): 對 g 的每個 p，send(p, m)
receive(m) at p: B-deliver(m)

問題：當成員很多時會發生 ack-implosion（確認爆炸）——大量 ack 同時湧回發送者，緩衝區爆滿、開始丟 ack，於是又重送、更多 ack…惡性循環浪費頻寬。

可靠群播 R-multicast 的三性質

• Integrity（完整性）：正確程序最多交付 m 一次，且 m 確實是某個合法 sender 送的。
• Validity（有效性）：若正確程序群播 m，它終究會交付 m（對發送者的活躍性保證）。
• Agreement（一致性）：若一個正確程序交付了 m，則群組裡所有正確程序終究都會交付 m。

生活妙喻

群組公告的『全有或全無』

比喻：班級群組轉發公告

老師要在班級群組發一則重要公告（群播）。

• 基本群播 B-multicast 像老師一個一個私訊每位同學。問題是：老師若私訊到一半手機沒電，有人收到、有人沒收到，公告就不一致了。而且全班同時回『收到』會把老師的訊息塞爆（ack-implosion）。

• 可靠群播的 agreement 就像約定：『只要有任何一個同學看到公告，就有義務確保全班都看到』。這樣即使老師中途斷線，只要有一個人轉發出去，公告就會傳遍全班——這就是 atomicity（全有或全無）。

在 B-multicast 之上做可靠群播

訣竅就是把上面的約定寫成演算法：

flowchart TD
  A[要 R-multicast m] --> B[先 B-multicast m 給群組含自己]
  B --> C[某成員 B-deliver 收到 m]
  C --> D{以前收過 m 嗎}
  D -- 沒收過 --> E[記下 m 並轉發 B-multicast 給群組]
  E --> F[然後才 R-deliver m]
  D -- 收過 --> G[丟棄重複]

關鍵順序：先轉發、再交付。每個正確程序在交付前都會幫忙再廣播一次，所以只要有一個正確程序交付，其他正確程序也終會收到。

實用超能力

效率改良與 uniform 性質

這個簡單演算法的代價

上面『收到先轉發』的做法在非同步系統正確，但很沒效率：每則訊息會被送到每個程序 N 次（每個人都轉發一遍）。

用 IP multicast 改良

實務上可結合 IP multicast + 捎帶確認（piggybacked ack）+ 否定確認（negative ack）：

• 平常不發獨立 ack，而是把 ack 捎帶在自己要送的訊息上。
• 只有偵測到漏收訊息時，才送否定確認（NACK） 去要回缺的訊息。
• 用序號搭配 hold-back queue 來判斷有沒有漏收。

uniform 一致性

更強的版本叫 uniform agreement（一致的一致性）：

只要有任何程序（不論它是否正確、會不會稍後當機）交付了 m，所有正確程序終究都會交付 m。

為什麼有用？想像一群銀行帳戶副本伺服器。某伺服器交付了一筆更新、被客戶看到、然後它當機了。若沒有 uniform agreement，這筆別人都沒處理的更新就會造成可觀察的不一致。前面『先轉發再交付』的演算法剛好滿足 uniform agreement；若把『轉發』和『交付』兩行對調，就不再滿足了。

深度探秘

光是『都收到』還不夠

為什麼順序重要

基本群播交付訊息的順序是任意的（因底層一對一傳遞延遲不一）。但很多應用受不了這點——例如核電廠裡，『安全威脅事件』與『控制單元動作』必須被所有程序以相同順序觀察。

常見三種排序（先假設每個程序只屬於一個群組）：

• FIFO ordering：若同一個正確程序先 multicast m、再 multicast m′，則每個交付兩者的正確程序都會先交付 m 再交付 m′。（同一發送者的順序）
• Causal ordering（因果序）：若 multicast(m) happened-before multicast(m′)（由群組內訊息引發的因果關係），則任何交付兩者的正確程序都先交付 m 再交付 m′。
• Total ordering（全序）：若一個正確程序先交付 m 再交付 m′，則任何其他交付兩者的正確程序也都先交付 m 再交付 m′。（大家順序一致，但不限定是哪種順序）

生活妙喻

群組聊天的三種秩序

比喻：班級群組的訊息秩序

• FIFO：A 同學先發『我餓了』再發『我們去吃飯』，那麼每個人看到 A 的這兩句，順序都一樣（先餓再吃飯）。但 A 的訊息和 B 的訊息之間沒規定。

• 因果序：B 看到 A 的『我們去吃飯』後回了『好啊！』。那麼任何人看到 B 的『好啊』，一定也先看過 A 的那句邀約——回覆不會跑到原訊息前面。

• 全序：不管內容有沒有關聯，全班看到所有訊息的順序完全一致，所以大家可以用『第 24 則訊息』來指同一則，不會雞同鴨講。

它們的關係

flowchart TD
  A[因果序 Causal] --> B[蘊含 FIFO]
  C[全序 Total] --> D[與FIFO因果獨立]
  D --> E[可組合成 FIFO-total 或 causal-total 混合序]

因果序蘊含 FIFO（同一程序的兩個群播本來就有 happened-before 關係）。但全序和前兩者獨立：全序只要求『大家一致』，那個一致的順序甚至可能和實際送出的時間相反！全序也不一定是 FIFO 或因果——所以才有 FIFO-total、causal-total 等混合版。

實用超能力

佈告欄例子與 hold-back queue

佈告欄的實例

佈告欄程式裡，每個討論主題是一個群組。看 Figure 15.12 的顯示：

• 要保證每位使用者看到 A.Hanlon 的貼文順序一致 → 至少要 FIFO。
• 『Re: Mach』(27) 不能跑到原文『Mach』(23) 前面 → 需要因果序。
• 若要大家都能用『第 24 則』指同一篇 → 需要全序。

（實務上 USENET 兩者都不做，因為大規模下成本太高，划不來。）

hold-back queue 的角色

排序怎麼實作？靠 hold-back queue（暫存佇列）：訊息到了先不交付，丟進暫存佇列，等『該交付的條件滿足』（例如序號連續、因果前置都到齊）才移到交付佇列。

排序的代價：可能為了等一則它其實不依賴的訊息，而不必要地延遲交付，增加延遲與頻寬。注意排序本身不蘊含可靠性，兩者可分別組合（可靠＋全序＝atomic multicast）。

深度探秘

三種排序怎麼真的做出來

FIFO 序：用『每發送者』序號

做法和一對一通訊類似：發送者 p 對群組 g 維護計數 $S^p_g$（已送幾則）。每送一則就把 $S^p_g$ 捎帶上去再加 1。收方對每個來源 q 記住 $R^q_g$（最近交付的序號）。收到序號 S 的訊息時，只有當 $S = R^q_g + 1$（剛好是期待的下一則）才交付，否則丟進 hold-back queue 等。

全序：序號要『大家一致』

全序的核心是給訊息全序的識別碼，讓每個程序依相同識別碼做相同排序決定。兩種主流做法：

1. 序列器（sequencer）：指定一個程序當『發號員』。要 TO-multicast 的訊息送給序列器與群組，序列器維護群組序號 $s_g$，依收到順序指派遞增序號，再 B-multicast 一個 order 訊息公告序號。缺點：序列器是瓶頸與單點失效。

2. 分散式協商（ISIS 演算法）：大家一起喊價談出 agreed 序號（下一步詳述）。

生活妙喻

發號碼牌 vs 大家喊價

全序做法一：序列器＝銀行發號機

像銀行入口的抽號碼機：不管你從哪個窗口來，都先去抽一張號碼牌（序列器指派的序號），大家依號碼牌順序辦理。號碼是唯一發出的，所以全序自然成立。

缺點顯而易見：號碼機壞了（單點失效）或人太多排隊抽號（瓶頸）就卡住。

全序做法二：ISIS＝大家喊價談共識

沒有發號機時，讓大家協商出序號：

flowchart TD
  A[發送者 B-multicast 訊息加唯一 id] --> B[每個收方提議一個序號 Pq = MaxAq,Pq + 1]
  B --> C[收方暫放 hold-back queue 依提議序號排序]
  C --> D[發送者收齊提議 取最大者當 agreed 序號 a]
  D --> E[發送者廣播 agreed 序號 a]
  E --> F[收方更新並重新排序 到隊首才交付]

每個程序 q 記住已見過的最大 agreed 序號 $A^q_g$ 與自己最大的提議序號 $P^q_g$。每個人提議 $\max(A^q_g, P^q_g)+1$，發送者取所有提議中最大值當最終 agreed 序號廣播回去。代價：延遲較高，要三趟序列訊息才能交付一則。

實用超能力

因果序用向量時戳

因果序：靠向量時戳判斷因果

每個程序 $p_i$ 維護一個向量時戳 $V_i$，每個分量計數『來自各程序、且因果上早於下一個要送訊息』的群播數。

• 要 CO-multicast 時：把自己分量 $V_i[i]$ 加 1，連同時戳一起 B-multicast。
• 收到來自 $p_j$ 的訊息時，先放 hold-back queue，等到滿足兩個條件才 CO-deliver：
  • (a) 已交付 $p_j$ 之前送的所有訊息；
  • (b) 已交付所有『$p_j$ 在送這則時就已交付過』的訊息。

這兩個條件都能用比較向量時戳判斷。交付後把對應分量加 1。

組合與限制

• 用 R-multicast 取代 B-multicast → 得到可靠又因果序的群播。
• 把因果序協定接上序列器全序協定 → 得到又全序又因果的交付。
• 以上演算法都假設非重疊群組。實務上程序常加入多個重疊群組，需擴充為 global ordering，較複雜。

直覺：向量時戳就像每則訊息附帶一張『我之前看過哪些訊息』的清單，
收方對照清單，確認該先看的都看了，才把這則交付。

深度探秘

把所有一致問題抽象成『共識』

共識問題的定義

共識（consensus） 是這樣的：每個程序一開始處於 undecided 狀態，各自提一個值 $v_i$（取自某集合 D）。程序互相交換值後，各自設定決策變數 $d_i$，進入 decided 狀態，之後 $d_i$ 不能再改。

三個必須成立的條件：

• Termination（終止性）：每個正確程序最終都會設好決策變數。
• Agreement（一致性）：所有正確程序的決策值相同（$d_i = d_j$）。
• Integrity（完整性，又稱 validity）：若所有正確程序提的值都一樣，則任何進入 decided 狀態的正確程序選的就是那個值。

無失效時很簡單

若程序不會失效，共識超好解：每個程序可靠群播自己的提議，收齊全部 N 個值後，套用 majority（取最多數的值，無多數則回特殊值 $\bot$）。大家收到相同集合、算相同函數，自然一致。majority 只是其中一種，也可用 minimum、maximum。

但程序會 crash 就麻煩了（要偵測失效，且在非同步系統可能無法終止）；Byzantine（任意）失效更糟——壞程序可亂送、對不同人說不同話。

生活妙喻

太空船該繼續還是中止

比喻：太空船控制電腦投票

三台控制電腦要決定『任務 proceed 還是 abort』。兩台提 proceed，第三台提 abort 後當機了。兩台存活的正確電腦最後都決定 proceed——這就滿足共識：

• 終止：兩台都做出了決定。
• 一致：兩台決定相同（都 proceed）。
• 完整：（修正版）若大家提一樣的值就選那個。

三個近親問題

flowchart TD
  A[共識 Consensus 每人提一值 大家決定同一值] 
  B[拜占庭將軍 BG 一個司令發值 可能說謊]
  C[互動一致性 IC 大家對一整個向量達成一致]
  A -.可互相轉換.- B
  B -.可互相轉換.- C
  C -.可互相轉換.- A

• 拜占庭將軍（Byzantine generals）：由一個司令發出值，其他副官要對它達成一致。但司令或副官可能叛變說謊（對不同人說不同話）。與共識不同在『一個指定者發值』。
• 互動一致性（interactive consistency）：每個程序提一個值，大家要對一整個向量（每個程序一格）達成一致。

實用超能力

問題之間可以互相轉換

為什麼要研究它們的關係

共識、拜占庭將軍（BG）、互動一致性（IC）可以互相推導——解出一個，就能拼出另一個。這很有用：增進理解，也能重用解法、省下實作成本。

設 $C_i$、$BG_i$、$IC_i$ 分別是三個問題的解所得到 $p_i$ 的決策值：

• IC from BG：把 BG 跑 N 次，每次讓不同程序當司令，蒐集成向量。
• C from IC（多數程序正確時）：跑 IC 得到向量，再對向量套 majority 取出單一值。
• BG from C：司令把值送給大家，所有程序拿收到的值跑 C，得到的就是決策值。

共識 ≡ 可靠且全序群播

在 crash 失效下，共識等價於『可靠且全序群播（RTO-multicast）』——有一個就能解另一個。

用 RTO-multicast 解共識：把程序集成群組，每個程序 RTO-multicast 自己的值，然後大家都選第一個被交付的值當決策值。

• 終止：來自群播的可靠性。
• 一致與完整：來自群播的可靠性與全序（大家第一個交付的必然相同）。

反過來，Chandra 與 Toueg 也證明可從共識導出可靠全序群播。這個等價關係是後面不可能定理的重要伏筆。

深度探秘

同步系統下，crash 共識可解

同步系統的 crash 共識：f+1 輪

假設最多 f 個程序會 crash。Dolev-Strong 演算法分**回合（rounds）**進行，每回合正確程序互相 B-multicast 它們知道、但上回合還沒送過的值。

• 變數 $Values^r_i$ 存程序 $p_i$ 在第 r 回合開始時已知的提議值集合。
• 每回合送出新學到的值，並收下別人送來的、記下新值。
• 每回合用 timeout 限制時長（同步系統做得到）。
• 跑完 $f+1$ 回合後，每個程序選收到值集合的 minimum 當決策值。

為什麼是 f+1 輪

關鍵直覺：要讓某個值 v 出現在某程序卻沒出現在另一程序，必須有『送 v 的程序在送達前就 crash』。順著推，每一回合都得至少死一個程序才能持續造成不一致。但最多只有 f 個會 crash，而有 $f+1$ 回合——抽屜原理告訴我們，必有一回合沒人死，那回合後大家的值集合就一致了。

$$\text{容忍 } f \text{ 個 crash 的共識} \Rightarrow \text{至少需要 } f+1 \text{ 輪}$$

生活妙喻

傳話遊戲與軍中叛徒

f+1 輪＝多傳幾輪確保話傳到

想像一群人玩傳話，每輪把自己知道的新消息告訴大家。只要每輪『最多一個人會中途離席』，那麼多玩一輪（比可能離席的人數多一輪），就一定有某一輪『全員到齊把話傳完』，之後大家知道的消息就一樣了。

拜占庭將軍：叛徒會說謊

如果失效是任意（Byzantine） 的——叛徒會對甲說攻、對乙說退——情況就嚴峻多了。

flowchart TD
  A[司令發令] --> B[副官2收到 攻]
  A --> C[副官3收到 攻]
  B --> D[副官2轉告副官3 攻]
  C --> E[副官3轉告副官2 但叛徒亂傳 退]
  E --> F[副官2收到矛盾 攻與退 分不出誰是叛徒]

三個將軍、一個叛徒就無解：當你收到兩個互相矛盾的值，根本分不出是司令說謊還是同僚說謊。Lamport 等人證明：未簽章（口頭）訊息下，N ≤ 3f 時無解。

實用超能力

N>3f 與四將軍的多數決

拜占庭共識的門檻：N > 3f

Lamport 等人證明：未簽章訊息下，要解拜占庭將軍問題必須 $N \geq 3f+1$（即 N > 3f）。直覺：要靠多數決蓋過叛徒的雜訊，正確的人就得夠多。

四將軍、一叛徒的解法（N=4, f=1）

兩回合訊息：

1. 第一回合：司令把值送給每位副官。
2. 第二回合：每位副官把收到的值轉告其他副官。

之後每位正確副官手上有：司令給的值 + 其他副官轉來的值，共 $N-1$ 個。套多數函數：

• 若司令是叛徒：副官全正確，會蒐到司令發出的同一組值，多數決得出一致結果。
• 若某副官是叛徒：因 $N-2 \geq 2$，正確值佔多數，叛徒亂傳的單一假值會被多數決忽略。

成本與簽章

• 未簽章時，Lamport 演算法需 $f+1$ 回合、$O(N^{f+1})$ 則訊息——非常昂貴。Fischer-Lynch 證明任何確定性拜占庭共識至少要 $f+1$ 回合。
• 用數位簽章（signed/簽章訊息）可大幅降低成本：叛徒無法謊報別人說過的話，Dolev-Strong 簽章版只要 $O(N^2)$ 則訊息。對付惡意攻擊者，幾乎一定要用簽章。

深度探秘

FLP：非同步系統的當頭棒喝

那個震撼的不可能定理

前面的共識解法都假設系統是同步的——靠回合與 timeout 運作。那非同步系統呢？

Fischer、Lynch、Paterson（FLP，1985）證明了分散式系統理論中最有名的結果之一：

在非同步系統中，即使只有一個程序發生 crash 失效，也沒有任何演算法能『保證』達成共識。

核心原因：在非同步系統，程序可在任意時間回應訊息，所以當機的程序和只是很慢的程序完全無法區分。證明（超出本書範圍）顯示總存在某種執行的延續，讓共識永遠達不成。

連鎖效應

由前一節『問題互相等價』可知，FLP 立刻推出：非同步系統也無法保證解出拜占庭將軍、互動一致性、以及可靠且全序的群播。否則就能反推出共識的解，與 FLP 矛盾。

生活妙喻

『保證』兩個字是關鍵

注意『保證』這個詞

FLP 不是說『非同步系統永遠無法達成共識』。它說的是無法 100% 保證。共識仍可能以大於零的機率達成——這也符合我們的日常經驗：銀行交易系統明明常常是非同步的，卻年復一年穩定地達成一致。

比喻：約朋友碰面

你和朋友用會延遲又不知何時送達的訊息約碰面（非同步），而且其中一人可能臨時不見（crash）。

• 你無法設計一套規則保證每次都約成功——因為對方沒回，你永遠分不清他是還在路上、還是已經放你鴿子。
• 但實務上你們大多數時候還是約成功了，因為現實沒那麼壞心。

flowchart TD
  A[非同步系統 一個crash] --> B[無法保證達成共識 FLP]
  B --> C[繞道一 遮罩失效]
  B --> D[繞道二 失效偵測器]
  B --> E[繞道三 隨機化]

FLP 中那個『對手 adversary』就像專門搞破壞的霉運：剛好在最糟的時機延遲訊息、放慢程序，讓你永遠差一步。

實用超能力

三種實務繞道法

既然無法保證，實務怎麼辦？

有三種繞過 FLP 的常見技巧：

1. 遮罩失效（masking faults）

用持久儲存（persistent storage） 讓程序撐過 crash。程序在關鍵點把足夠資訊寫入持久儲存，crash 重啟後讀回繼續，表現得像個只是偶爾很慢的正確程序。交易系統就是這麼做的。

2. 用失效偵測器

讓程序約定：超過一定時間沒回應就『當作』它失效，並丟棄它之後的訊息——等於把非同步系統人為變成同步系統（ISIS 系統的做法）。

• 缺點：timeout 要設長才準，但這逼大家空等很久。
• 進階：Chandra-Toueg 證明，只要少於 $N/2$ 程序 crash 且通訊可靠，用eventually weak failure detector（最終弱失效偵測器）就能解共識，還允許被誤疑的程序繼續正常運作，不浪費它們。

3. 隨機化（randomization）

FLP 的『對手』靠精準算計你的狀態來搞破壞。若在程序行為中加入隨機性，對手就無法穩定地施展破壞策略，使程序能在有限的期望時間內達成共識（即使某些情況仍達不成）。Canetti-Rabin 給出連 Byzantine 失效都能解的機率式演算法。