Paxos: majority intersection preserves one chosen value

Single-decree Paxos chooses one value despite crash failures and message loss, duplication, delay, or reordering. A proposer first gathers promises for a unique ballot from a majority. It must propose the value attached to the highest previously accepted ballot in those replies, or its own value if none was accepted. A value becomes chosen only after a majority accepts it.

With 2f+1 acceptors, any majority has f+1 members and any two majorities intersect. Stable promises and accepted records carry the safety chain across crashes. One distinguished proposer improves liveness, but leader election is not the safety proof; dueling proposers can stall without choosing conflicting values.

Prerequisites and model

• Failures are crash-stop or crash-recovery, not Byzantine; messages are not forged or corrupted.
• Ballot numbers are globally unique and monotonically increased by proposers.
• Each acceptor durably stores its highest promise and accepted ballot/value before replying.
• Multi-Paxos runs the invariant per log slot and applies only a contiguous chosen prefix.

Correctness claims and invariants

• PAX-C1. A value is chosen only after acceptance by a majority; majority intersection is the safety hinge.
• PAX-C2. After prepare, a proposer carries forward the value from the highest accepted ballot reported by its majority.
• PAX-C3. Promises and accepted records must survive restart before the corresponding response.
• PAX-C4. Multiple proposers do not break safety but can livelock; progress needs an eventual distinguished proposer and a reachable majority.
• PAX-C5. A learner may not immediately know a chosen value when notifications are lost; later protocol traffic can recover it.
• PAX-C6. Multi-Paxos leaders recover or fill log gaps before applying later slots.
• PAX-C7. Paxos Commit is a separate consensus-backed atomic-commit construction, not ordinary single-decree Paxos.

What the scenarios prove

• Prepare and promise majority (prepare-promise-majority): A proposer obtains durable promises and must adopt the highest accepted value returned.

• Majority acceptance chooses one value (accept-chosen-value): Two of three durable accepts form a chosen certificate; the third may be unavailable.

• Competing proposers and retry (competing-proposer): Higher ballots preempt lower ones; contention can stall but cannot choose two values.

• Leader failover recovers log gaps (leader-failover-gap): A new Multi-Paxos leader recovers missing slots before applying a later chosen suffix.

• Learner recovers chosen value (learner-recovery): Lost learner notifications do not unchoose a value; later proposal traffic reveals it.

• Stable storage across restart (stable-storage-restart): An acceptor reloads its promise before serving; forgetting it would violate safety.

Failure, concurrency, and retry traps

• A reused ballot number can attach two values to one identity.
• Acceptors that forget promises after restart can accept an unsafe lower ballot.
• Majority acceptance does not mean every learner already knows the value.
• A minority partition preserves safety by losing progress.
• Skipping a missing chosen log slot before applying later slots breaks state-machine order.

Boundaries and non-guarantees

• Classic Paxos does not tolerate Byzantine acceptors.
• Leader election is a liveness optimization, not the safety invariant.
• Quorum reachability does not provide availability in every network partition.
• A transaction commit protocol requires additional participant-vote semantics; see Paxos Commit.

Related material

Raft consensus is an explore diagram and is linked as Markdown.

Primary sources

1. Lamport, Paxos Made Simple
2. Paxos Made Simple PDF
3. Lamport, The Part-Time Parliament
4. Gray and Lamport, Consensus on Transaction Commit