Consensus 與 Paxos：用 Majority 保住唯一決策

Consensus 要 non-faulty process 在 failure／delay 下決定同一 value。Properties 很簡單：agreement、validity、termination；能否同時做到取決於 system model。

Fully asynchronous system 裡，delay 與 crash 無法區分。FLP 表示只要可能有一個 crash，deterministic consensus 就不能保證 termination；safety 仍能維持，實務系統也能在 timing favorable 時進展。

Paxos role 與 two phases

• Proposer： 用 numbered ballot 提議 value。
• Acceptor： promise、vote。
• Learner： 得知 chosen value。

Phase 1 請 majority promise 不再接受較低 ballot，並回報過去 accepted value。Phase 2 使用回報中 ballot 最高的 value；若不存在才用新 value，再請 majority accept。

prepare(n) ──> majority promises
accept(n, v) ──> majority accepts
v is chosen

Majority intersection 為什麼重要

任意兩個 majority 必定 overlap。若某 value 已被一組 majority 選定，後來 proposer 聯絡另一組 majority 時，至少會遇到一個保留舊決策證據的 acceptor；選 highest accepted ballot 就能把它延續。

白話來說： 新委員會不可能避開所有見證過舊決策的人。

多個 proposer 競爭時，系統可能沒有 progress，但 safety 仍成立。Stable-leader Multi-Paxos 則把 prepare phase 攤到一連串 log entry。

複習卡

• Consensus 將 agreement／validity 與 termination 分開。
• Asynchrony 使 failure 與 delay 無法區分。
• Paxos ballot 排序 competing round。
• Majority acceptance 選定 value。
• Quorum intersection 把舊決策帶到新 round。
• Stable leadership 改善 liveness／performance，不改 safety 核心。

進階閱讀：下學期的完整推演與圖解.