Consensus and Paxos: Majorities Preserve One Decision

Consensus asks non-faulty processes to decide one value despite failures and delay. The properties are easy to state: agreement, validity, and termination. Achieving all three depends on the system model.

In a fully asynchronous system, delay and crash are indistinguishable. FLP shows that deterministic consensus cannot guarantee termination with even one possible crash, although safety can still hold and practical systems can make progress under favorable timing.

Paxos roles and two phases

Proposer: suggests a value with a numbered ballot.
Acceptor: promises and votes.
Learner: discovers the chosen value.

Phase 1 asks a majority of acceptors to promise not to accept lower ballots and report prior accepted values. Phase 2 proposes the highest-ballot value already reported, or a new value if none exists, then asks a majority to accept.

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

Why majority intersection matters

Any two majorities overlap. If a value was chosen by one majority, a later proposer contacting another majority must encounter at least one acceptor carrying evidence of it. Choosing the highest accepted ballot preserves that value.

In plain terms: a new committee cannot avoid every member who witnessed the old decision.

Multiple competing proposers can prevent progress even while safety holds. Stable-leader Multi-Paxos amortizes the prepare phase for a sequence of log entries.

Review card

Consensus separates agreement/validity from termination.
Asynchrony makes failure indistinguishable from delay.
Paxos ballots order competing rounds.
A majority acceptance chooses a value.
Quorum intersection carries prior decisions forward.
Stable leadership improves liveness and performance, not safety fundamentals.

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 核心。