Paxos

How Paxos Works

Paxos solves the problem of getting a group of unreliable nodes to agree on a single value — the consensus problem. It was described by Leslie Lamport in 1989, and despite its reputation for being hard to understand, the core idea is surprisingly elegant.

There are three roles: proposers suggest values, acceptors vote on them, and learners find out what was chosen. (In practice, nodes often play multiple roles. Here we keep them separate for clarity.)

The protocol has two phases:

Phase 1 — Prepare/Promise. A proposer picks a proposal number n (higher than any it's used before) and sends PREPARE(n) to all acceptors. Each acceptor checks: is n higher than anything I've already promised? If yes, it promises not to accept any proposal numbered lower than n, and replies with any value it has already accepted. If no, it rejects (NACK).

Phase 2 — Accept/Accepted. If the proposer gets promises from a majority of acceptors, it can proceed. But here's the crucial constraint: if any acceptor's promise included a previously accepted value, the proposer must use the value from the highest-numbered accepted proposal — not its own preferred value. This is what makes Paxos safe. The proposer sends ACCEPT(n, value) to all acceptors. Each acceptor checks: have I promised anything higher than n? If not, it accepts and replies ACCEPTED.

When is a value chosen? Once a majority of acceptors have accepted the same proposal number, that value is chosen. No other value can ever be chosen — any future proposer that gets a majority of promises will see the accepted value and be forced to re-propose it.

Competing proposals. This is where Paxos gets interesting. Try proposing from both P1 and P2. If P1 sends PREPARE(1) and gets promises, but then P2 sends PREPARE(2) before P1's ACCEPT arrives, the acceptors promise to P2 instead. When P1 tries to ACCEPT(1, A), the acceptors reject it — they've promised higher. P1 has to start over with a higher number. This can lead to livelock where proposers keep outbidding each other, which is why practical systems use a leader to reduce contention.

Why the majority quorum matters. Any two majorities overlap in at least one node. So if a value was accepted by a majority, any future proposer that contacts a majority will hear about it through at least one acceptor. This is the deep insight: you don't need all nodes to agree, just enough that every future attempt will discover what happened.

Try killing an acceptor and proposing — it still works with 2 of 3. Kill two and no majority is possible. Propose from both P1 and P2 quickly to see competing proposals and NACKs.