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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.