讓一群節點就某個值達成一致，即使有節點崩潰、訊息延遲。Paxos 是最廣為人知的共識演算法（Lamport 1998），以正確性為先——在任意數量故障下都保證安全，只要多數派存活就能繼續推進。它是一整個協議家族，Raft 則是後來為「好懂」而生的另一條路。
🧠 Intuition
TIP
Paxos = 「先問夠多人拿到承諾，再叫這夠多人把值記下來」。每次提案都帶一個單調遞增的號碼當身分證；靠「任兩個多數集合必定相交」這條幾何事實，保證一旦有值被決定，之後的提案者一定會看到它、只能沿用它——決定就不反悔。
- 三種角色：proposer（收客戶端的值、發起提案、收集投票）、acceptor（投票接受或拒絕提案，容錯需要多個、活性只需多數派）、learner（副本，記下已決定的結果）。實務上一個程序常同時兼任三者。
- 每個提案 = 一個值 + 一個唯一且單調遞增的提案號碼（常以
(id, timestamp)實作）。 - 分兩階段：Prepare → Promise（選出這輪的資格）、Accept → Accepted（真正複製值）。
- 安全性的根：quorum（多數派）——任兩個多數集合至少有一個共同成員，這個共同成員負責把舊決定「帶」給新提案者。
⚖️ Tradeoffs
兩階段流程 — Prepare/Promise 與 Accept/Accepted
- Phase 1（Propose）：proposer 對多數 acceptor 送
Prepare(n)。acceptor 若沒回應過更高號碼，就承諾不再接受號碼更低的提案；若已接受過某提案，回Promise時附上已接受的值。 - Phase 2（Replication）：收集到多數 promise 後，proposer 送
Accept!(n, v)。這裡的v不是隨便挑的——若 promise 回應中有已接受的提案，必須採用其中號碼最高的那個值；沒有才用自己的值。 - acceptor 收到
Accept!(n, v)就接受，除非期間已對更高號碼的 Prepare 承諾過。 - 一個值被多數 acceptor 接受即算決定；learner 收到多數 acceptor 的通知後得知結果。
提案號碼與多數決 — 安全性從何而來
- quorum 只描述阻塞性質：每一步都要等到至少一個多數派回應才前進，但不必等全部。
- 核心不變式：任兩個多數集合必相交。所以只要某值已被一個多數派接受，任何新的 proposer 在 Phase 1 一定會撞到「見過那個值」的 acceptor，於是被迫沿用它。
- 這保證了一旦決定就不反悔：後續 proposer 即使用更高號碼開新輪次，也只能決定相同的值。
- 容錯代價：要容忍 f 個故障，安全在任意數量故障下都成立，活性則需總共 2f + 1 個程序。
- 活鎖風險：兩個 proposer 互相用更高號碼壓過對方、誰都跑不完 Phase 2，靠隨機退避 (random backoff) 化解。
Multi-Paxos — 穩定 leader 省掉 Phase 1
- 經典 Paxos 每決定一個值都要跑一次完整 Prepare 輪次，昂貴。
- Multi-Paxos 引入長期 leader（distinguished proposer）：leader 一旦確立，後續複製可跳過 Phase 1、直接進 Accept，並連續複製多個值。
- 常被描述為操作的複製日誌 (replicated log)：單值 Paxos 像「一次性寫入暫存器」，Multi-Paxos 像「僅追加日誌」。
- 部分實作用 lease：leader 週期性告知自己還活著，參與者承諾 lease 期間不接受別的 leader，藉此直接從 leader 讀而不必收 quorum。
- 但 lease 是效能優化、不是正確性保證，且依賴有界時鐘同步——時鐘漂移過大時線性化保證會失守。
- 日誌需定期做快照 (snapshot) 並截斷，否則無限增長。
變體家族 — Fast / EPaxos / Flexible
- Fast Paxos：讓 proposer 直接聯繫 acceptor、繞過 leader 少一次往返，代價是 quorum 變大（需 3f + 1 個 acceptor）；多個 proposer 同時搶 fast round 會碰撞，高請求率下延遲反而可能更差。
- EPaxos：不設固定 leader，讓每個命令有自己的 leader，靠找出命令間的依賴關係建立順序而非靠提案號碼；只有真正互相干擾的命令才需排序，兼顧高可用與高吞吐。
- Flexible Paxos：關鍵洞見是只需 Phase 1 的 quorum 與 Phase 2 的 quorum 有交集即可，即
Q1 + Q2 > N；於是可縮小較頻繁的 Phase 2 quorum、把票數挪到選舉階段，用可用性換延遲。 - 共通主題：都在動「要等多少人、由誰發起、如何排序」這三個旋鈕，換取延遲、吞吐或可用性。
與 Raft 對比 — 家族/正確性 vs 單一/可理解性
- Paxos 是一個協議家族，論文以正確性為先，出了名地難懂、難正確實作；Raft 是單一演算法，設計目標明寫在標題：「尋找一個可理解的共識演算法」。
- Raft 把 leader 設為一等公民、日誌不允許有洞、只從 leader 流向 follower，換取好懂好測；Paxos 較自由但更難推理（詳細內部見 raft 頁，此處不展開）。
- 兩者解的是同一問題：原子廣播與共識在有崩潰故障的非同步系統中等價，replicated log 就是全序廣播的實作。
- 工程現實：etcd / Consul / CockroachDB 等多選 Raft——好懂往往勝過理論優雅；但 Paxos 家族（尤其 Multi-Paxos）仍是許多正式系統的底層。
🔑 Takeaways
- Paxos 三角色 proposer / acceptor / learner，兩階段 Prepare→Promise / Accept→Accepted，每個提案帶單調遞增號碼當身分。
- 安全性靠 quorum 相交：任兩多數集合必有共同成員，逼新提案者沿用已決定的值——一旦決定就不反悔；容錯需 2f + 1 個程序。
- Multi-Paxos 用穩定 leader 省掉 Phase 1、連續複製成一條複製日誌；lease 是效能優化而非正確性保證，依賴有界時鐘同步。
- 變體都在調「等多少人 / 誰發起 / 如何排序」：Fast（少一跳、quorum 更大）、EPaxos（依賴排序、無固定 leader）、Flexible（只要兩階段 quorum 相交）。相對 Raft，Paxos 是以正確性為先的協議家族，Raft 賭的是可理解性。
No notes yet — jot your takeaways or Q&A here.