Notesdistributed🌱 seedling
Paxos
Also: Multi-Paxos · Basic Paxos · Single-Decree Paxos · Flexible Paxos · Synod Algorithm
A consensus algorithm in which a proposer gets promises from a majority of acceptors (phase 1), then asks them to accept a value (phase 2), adopting any value already accepted. Multi-Paxos keeps a stable leader so phase 1 runs once for a whole log.
Why it exists
Nodes need to agree on a value while proposers compete, crash and restart, and messages are lost or delayed. Paxos guarantees a single chosen value, and its safety never depends on timing.
How it works
- Prepare(n): acceptors promise to ignore proposals numbered below n and report the highest-numbered proposal they've accepted.
- Accept(n, v): with a majority of promises, the proposer sends v = the value of the highest-numbered reported proposal, or its own if none. A value accepted by a majority is chosen.
- Any two majorities overlap, so a later proposer always learns a chosen value and re-proposes it.
- Proposal numbers fence stale proposers: an acceptor that promised n rejects anything lower.
- Multi-Paxos: one leader runs phase 1 once, then only phase 2 per log slot.
- Flexible Paxos: every phase-1 quorum must intersect every phase-2 quorum; phase-2 quorums needn't intersect each other.
Trade-offs
| Gains | Costs |
|---|---|
| minimal, proven safety core | the paper leaves much unspecified (membership, log compaction) |
| any node may lead and catch up in phase 1 | duelling proposers can livelock without a stable leader |
| flexible quorums for cheaper writes | notoriously hard to implement correctly |
In practice
- Spanner: a Paxos group per split. DynamoDB: Multi-Paxos per partition with leader leases. Cassandra: lightweight transactions (compare-and-set) run Paxos. Chubby was built on it.
- Compared with Raft, the main difference is leader election: Raft only elects up-to-date nodes; Paxos lets any node lead.
Pitfalls
- Running basic Paxos per value with no stable leader: two proposers can keep pre-empting each other.
Connections
- Part of
- Consensus
- Learn first
- Quorum
- Contrasts with
- Raft
- Related
- Fencing TokenLeader Election
Recall
These cards are also in your review deck, scheduled with spaced repetition.