Consensus 與 Paxos：Leader 故障後，決策為什麼不會改變？

三個副本要決定 log 的下一筆指令。Leader 送出提案，兩個副本已經存好，leader 卻在公布結果之前故障。接手的人能不能改選另一筆指令？

Paxos 的做法，是讓後來的提案遵守 acceptor 已經保存的證據。與其只記住「多數決」，更值得理解的是：這份證據記錄什麼，以及新 leader 為什麼不能跳過它。先從時間假設比較清楚的同步模型開始。

1. Consensus 要保證什麼？

每個 process 提出一個值。決策一旦做出，就不能再改。

性質	要求	類型
Agreement	不同 process 的決策不能互相矛盾	Safety
Validity	決定的值必須有人提出；若所有人都提同一個值，就選那個值	Safety
Termination	每個未故障的 process 最終都會做出決策	Liveness

不同教材的定義略有差異。這裡的 agreement 也包含「已做出決策，之後才故障」的 process。故障模型是 crash，不包含說謊或惡意傳送訊息。輸入限制則排除了「永遠選 0」這種沒有實際用途的演算法。

**同步系統（synchronous）**有已知的訊息與處理時間上限，能據此安排回合。**非同步系統（asynchronous）**沒有這種可用的上限。這和程式有沒有使用 async、API 會不會阻塞執行緒，是不同層次的問題。

2. 同步共識為什麼執行 f + 1 個回合？

假設有 N 個 process，最多 f < N 個發生 crash-stop，通訊可靠。正常 sender 傳給正常 receiver 的訊息會在該回合結束前抵達；若 sender 在逐一傳送途中故障，可能只有部分人收到。

每個 process 保存「已知輸入值的集合」。每回合把新學到的值送給所有人，再合併收到的內容。完整執行 f + 1 回合後，各自選集合中的最小值。

known = {自己的輸入}
new_values = {自己的輸入}

重複 f + 1 次：
    把 new_values 傳給所有 process
    received = 這回合收到的所有值
    new_values = received - known
    known = known union received

決定 min(known)

min 只是大家共同遵守的確定性選擇規則。真正需要證明的是：存活者最後持有相同集合。

範例：一次故障，讓一個值晚一回合才傳開

設 f = 1。A 的輸入是 0；B、C 的輸入都是 1。

sequenceDiagram
    participant A as A：輸入 0
    participant B as B：輸入 1
    participant C as C：輸入 1
    Note over A,C: 第 1 回合
    A->>B: 傳送 0
    Note over A: 尚未傳給 C 就故障
    B->>C: 傳送 1
    C->>B: 傳送 1
    Note over B: known = {0, 1}
    Note over C: known = {1}
    Note over B,C: 第 2 回合
    B->>C: 轉送剛學到的 0
    Note over B,C: 都持有 {0, 1}；都決定 0

如果第一回合就停止，B 會選 0，C 會選 1。第二回合讓這個差異消失。

為什麼能推廣到 f + 1？假設某個存活者到最後一回合才收到一個值，另一個存活者還沒有。最後的 sender 必須在只傳給其中一人後故障。若它更早就知道這個值，早已能把值傳開，所以它也必須在前一回合，透過另一個「只傳一部分就故障」的 sender 才學到。沿著這條隱藏的訊息鏈往回追，必須有 f + 1 次不同 process 的故障，與最多 f 次的假設矛盾。

這個推理依賴回合的時間界線。若訊息可以任意延遲，沒收到就不能推斷 sender 已經故障。

3. Paxos 先把「投票」和「決策」分清楚

Basic Paxos 的一個 instance 只選定一個值，例如某個 log 位置的指令。對不同位置重複執行，才能形成複製的 log；ballot 編號不是 log 的位置。

名稱	意義
Proposer	用唯一、可排序的 ballot 嘗試讓某個值被選定
Acceptor	保存 promise 與接受過的 proposal
Learner	取得「某個值已被選定」的證據
Accepted	單一 acceptor 已記錄 `(ballot, value)`
Chosen	多數 acceptor 已接受同一個 `(ballot, value)`
Learned	某個 process 已知道 proposal 被選定

同一台機器可以兼任三種角色。三個 acceptor 的 majority 是兩個；五個的 majority 是三個。一般而言，2f + 1 個 acceptor 在故障 f 個後，仍有多數可用。但光是人數足夠，不能保證任意延遲或無止境競爭之下仍有進展。

Acceptor 需要保留最高的 promised ballot，以及最高的 accepted (ballot, value)。若要在 crash 後恢復，這些狀態必須持久保存，而且要先存好，再送 acknowledgment。Ballot 在 proposer 重啟後也不能重複；例如用 (counter, proposer ID)，依共同規則比較大小，來區分不同 proposer 的提案。

4. 兩個階段，再讓大家知道結果

Phase 1：prepare 與 promise。 Proposer 送出 prepare(n)。尚未承諾更高 ballot 的 acceptor，可以承諾以後拒絕低於 n 的 accept request，並回報自己接受過、ballot 最高的 proposal。

Proposer 收到多數對 n 的 promise 後，才選擇要送出的值：

若任何回覆帶有 accepted proposal，使用這批回覆中 accepted ballot 最高的那個值。
若所有回覆都沒有 accepted proposal，才可以選擇新的提議值。

Phase 2：accept。 Proposer 送出 accept(n, value)。Acceptor 若尚未承諾更高 ballot，就可以接受它。多數接受相同 proposal 時，這個值就已經 chosen。

Learning。 接受回報或決策公告，讓 learner 得知結果。公告是在傳達已經成立的決策，不是讓決策成立的瞬間。

sequenceDiagram
    participant P as Proposer
    participant A as Acceptor A
    participant B as Acceptor B
    participant L as Learner
    P->>A: prepare(7)
    P->>B: prepare(7)
    A-->>P: promise 7；尚未 accepted
    B-->>P: promise 7；尚未 accepted
    Note over P: 收到多數回覆；選擇 X
    P->>A: accept(7, X)
    P->>B: accept(7, X)
    Note over A,B: 都已持久記錄：X 此時已 chosen
    A-->>P: accepted(7, X)
    B-->>P: accepted(7, X)
    P-->>L: 公告 chosen X
    Note over L: L 此時才 learned X

圖中省略第三個 acceptor，因為三個當中的兩個就足夠。課程用 election、bill、law 的比喻介紹流程；這裡依照 Lamport 的 Paxos Made Simple，補上 prepare／accept 的精確規則。

5. 故障推演：Leader 還沒公布 X 就消失了

假設 acceptor 是 A、B、C，ballot 7 已完成 prepare。

步驟	A	B	C	結果
接受 ballot 7	接受 `(7, X)`	接受 `(7, X)`	尚未接受	A + B 已讓 X chosen
舊 proposer 故障	保留 `(7, X)`	保留 `(7, X)`	尚未接受	即使沒有公告，X 仍是 chosen
新 proposer 向 B + C prepare 8	不變	promise 8；回報 `(7, X)`	promise 8；回報無	新 proposer 必須選 X
接受 ballot 8	不變	接受 `(8, X)`	接受 `(8, X)`	再次選定 X，讓結果可以被得知

新 proposer 不需要先證明 ballot 7 曾取得多數。B 的 accepted proposal 就已經限制了這次嘗試。選值規則看的是 accepted 證據，不只看已經公告的決策。

flowchart LR
    Old["舊多數：A + B"] --> B["B 保留 accepted X"]
    B --> New["新 prepare 多數：B + C"]
    New --> Keep["Ballot 8 必須延續 X"]

為什麼一定要選最高 accepted ballot？

換一種情況：只有 A 接受過 (7, X)，X 尚未 chosen。Ballot 8 的 proposer 向 B、C prepare，兩人都沒有 accepted proposal，因此可以讓 B、C 接受 (8, Y)。Y 此時已 chosen。

Ballot 9 如果向 A、B prepare，就會收到 (7, X) 與 (8, Y)。它必須選 Y。若隨意挑一個回報值，就可能用 X 推翻已經 chosen 的 Y。

Quorum intersection 提供共同的 acceptor；promise 和選值規則則定義這份共同證據的意義。它們一起維持不變量：一旦某個 proposal 選定 X，更高 ballot 若成功，也必須選 X。共同的 acceptor 後來可能回報更高的 ballot，因此 safety 的推理也需要確保中間每次提案都延續同一個值。

6. 沒有選錯，不代表一定選得出來

兩個 proposer 可以一直打斷彼此。P 完成 prepare 10；在它的 accept request 抵達前，Q 已完成 prepare 11。P 被拒絕後改用 12，又讓 Q 的請求失效。整個過程沒有矛盾的決策，卻也一直沒有值被選定。

若有一個穩定 proposer，能和正常回覆的多數通訊，也沒有更高 ballot 持續干擾，就可以完成流程。實際系統透過 leader 選擇、重試和時間假設取得這種條件。Timeout 可以成為發起下一次嘗試的理由，但不能證明前一個 proposer 已經死亡。

Multi-Paxos 把這套機制用在一連串 log 位置，穩定 leader 可以攤平 prepare 的成本。接手時仍須保留既有 accepted value。Consensus 本身也不會自動消除 client 重試，更不會讓外部付款憑空獲得 exactly-once 保證。

FLP 證明會進一步說明：只要允許一個 process crash，就沒有確定性演算法能對每一種合法的非同步執行保證 termination。

檢查理解

多數已接受 X，但所有 acknowledgment 都延遲，X 算 chosen 嗎？ 算。接受動作讓事實成立；回覆讓其他人得知事實。
Prepare 只有一個 acceptor 回報 X，可以因為不確定有沒有多數就忽略它嗎？ 不行。必須遵守 prepare quorum 中最高 accepted ballot 的選值規則。
更高 ballot 可以清掉舊決策嗎？ 不行。它排序的是嘗試，仍須保住已 chosen 的值。
Eventually 等於有固定完成期限嗎？ 不等於。Paxos 的進展還需要合適的通訊與 leader 條件；只有非同步模型，不能提供無條件 termination 保證。

閱讀依據

本文依據提供的 Cloud Computing Concepts, Part 1 3.1 The Consensus Problem、3.2 Consensus in Synchronous Systems、3.3 Paxos, Simply 投影片與逐字稿整理，範例及圖解另行繪製。Accepted／chosen／learned 的區別與精確選值規則，另核對上方連結的 Paxos Made Simple 第 2.2–2.4 節。