Paxos Primer
The consensus algorithm that underpins every reliable distributed system you have ever used.
TL;DR
Paxos lets a group of nodes agree on a single value, even when messages are lost, reordered, or delayed. No node is special. No clocks are trusted. Just quorums and promises.
The Three Roles
Every node can wear three hats. A Proposer suggests a value. An Acceptor votes on it. A Learner observes the outcome. In practice, every node runs all three.
Two-Phase Commit, But Correct
Phase 1 is Prepare. The proposer picks a proposal number n and asks a majority of acceptors: will you promise to ignore anything lower than n? If they already accepted a value, they return it.
Phase 2 is Accept. If the proposer hears back from a majority, it sends the value — either the one it originally wanted, or the highest-numbered value any acceptor already accepted. Acceptors vote. A majority yes means the value is chosen.
Why a Majority?
Any two majorities overlap by at least one node. That single intersection carries the promise — no two proposers can ever get a majority for different values at the same proposal number. The math is brutally simple and airtight.
Key Insight
Paxos does not guarantee termination — a dueling-proposer livelock is possible. That is why real systems elect a distinguished proposer (Multi-Paxos leader). The safety property — no two different values ever chosen — holds regardless.
Multi-Paxos in One Breath
Running Paxos once per log entry is slow. Multi-Paxos elects a stable leader that skips Phase 1 for subsequent slots. The leader streams Accept requests; acceptors vote. This is the backbone of Chubby, Spanner, and every serious consensus log.