Day 8: Paxos

Phase 1 · May 27, 2026

Agenda (2–3 hours)

• Read (45 min): Lamport "Paxos Made Simple" (2001) — only 14 pages
• Study (45 min): Trace through the two-phase protocol with a concrete example; identify all failure cases
• Practice (45 min): Draw message flow diagrams for normal case, proposer crash after phase 1, and proposer crash after phase 2a
• Challenge (30 min): What guarantees does Paxos make? What can go wrong if you skip the "prepare" phase?

The Consensus Problem

Given a set of processes that may fail (crash-stop), agree on a single value:

• Safety: all processes that decide, decide the same value
• Liveness: every non-faulty process eventually decides
• Validity: the decided value was proposed by some process

FLP Impossibility (Fischer, Lynch, Paterson 1985): no deterministic algorithm can guarantee both safety and liveness in a fully asynchronous system with even one crash failure.

Paxos sidesteps FLP by guaranteeing safety always and liveness only when the network is eventually synchronous.

Paxos Made Simple: Roles

• Proposer: wants to get a value accepted; sends Prepare and Accept messages
• Acceptor: votes on proposals; remembers highest ballot number promised
• Learner: learns the decided value (passive)

Single-decree Paxos decides one value. Multi-Paxos extends this to a log of values.

Paxos Protocol: Two Phases

Phase 1 (Prepare):

1. Proposer picks ballot number n > any seen
2. Sends Prepare(n) to a quorum of acceptors
3. Acceptors respond Promise(n, v_accepted) — promise not to accept any ballot < n
4. If acceptors previously accepted a value, they return it

Phase 2 (Accept):

1. Proposer picks value: either the highest-ballot value returned in phase 1, or its own value if none
2. Sends Accept(n, v) to quorum
3. Acceptors accept if they haven't promised a higher ballot
4. Learners are notified of the accepted value

Safety Analysis

Why can't two different values be decided?

If value v is decided in ballot n, it was accepted by a quorum Q1.
Any future ballot n' > n must contact a quorum Q2.
Since any two quorums overlap (|Q1| + |Q2| > N), the proposer in ballot n' will see v in phase 1 and must propose v again.

The key invariant: any accepted value in the highest ballot returned in phase 1 must be proposed in phase 2.

Key Takeaways

• Paxos guarantees consensus with f failures using 2f+1 nodes and f+1 quorums
• Phase 1 establishes a ballot lease and discovers previously accepted values
• Phase 2 commits a value that cannot conflict with any prior consensus
• Paxos is correct but complex to implement correctly (Multi-Paxos, leader leases, reconfiguration all add subtlety)
• Raft was designed as a more understandable replacement — tomorrow

Tomorrow: Raft — the same guarantees as Paxos, with a design optimized for understandability.