Paxos

The problem: agree on one value, even when things break#

Picture three servers that together store one small piece of shared truth — say, the value in the first slot of a replicated log. Google's Chubby lock service works exactly like this: a small group of replicas has to agree on each entry in a tiny database, and every other Google system leans on that agreement. Two clients show up at the same moment. One wants the slot to hold the command set x = 5. The other wants set x = 8. The servers must agree on exactly one of these, and once they agree, that answer can never change.

This would be easy if machines never failed and messages always arrived. They don't. A server can crash at any instant — mid-decision, before replying, right after replying. A message can be dropped, delayed for a minute, or arrive out of order. There is no shared clock and no way to tell a crashed server apart from a slow one. The one thing we assume is that machines are honest: a server can go silent, but it never lies about what it accepted. (Tolerating liars is a harder problem called Byzantine consensus, and Paxos does not attempt it.)

The naive fix is to pick one server as the boss and let it decide. That works until the boss crashes — now nobody can decide, and the whole system is stuck. So we can't lean on any single machine. We need the group to agree even while some members are down or unreachable.

The trick is to require a majority — more than half the servers. This is the same quorum idea from /quorum: with three servers, any two form a majority, and here is why that number is magic. Any two majorities of the same group must share at least one server, because two groups of two, drawn from three, always overlap. So if one value is accepted by a majority, and later some other value tries to get accepted by a majority, at least one server is in both majorities — and that server remembers the first value. Overlap is the seed of the whole safety argument. Everything below is machinery to make sure that shared server actually forces the two majorities to agree.

The three roles#

Paxos describes the protocol in terms of three roles, not three machines. In a real system one server usually plays all three at once, but keeping them separate makes the logic clear.

• Proposer — puts a value forward and tries to get it chosen. In our example, the client wanting set x = 5 is behind a proposer. Several proposers can be active at the same time, each pushing its own value.
• Acceptor — votes. Acceptors are the memory of the system: a value is chosen only when a majority of acceptors have accepted it, and acceptors remember what they've promised and accepted. The three servers are the acceptors.
• Learner — finds out which value won, so it can act on it (apply the command, answer a client). A learner does no voting; it just needs to be told the outcome once a majority has accepted.

Phase 1: prepare and promise#

A proposer can't just tell the acceptors set x = 5 and count votes. If two proposers did that at once, some acceptors might accept one value and some the other, with no majority for either — deadlock. So before proposing any value, a proposer first earns the right to propose. That's Phase 1.

Every attempt to propose carries a proposal number: a number that is unique to that proposer and only ever goes up. Think of it as a priority tag — a higher number outranks a lower one. (Making them unique is simple in practice: each proposer draws from a separate set, like proposer P using 1, 4, 7 and proposer Q using 2, 5, 8, so two proposers can never pick the same number.)

1. The proposer picks a proposal number higher than any it has used, and sends a prepare(n) message with that number to the acceptors. It says nothing about the value yet — this is just a request to reserve the right to propose.
2. An acceptor that receives prepare(n) compares n to the highest prepare it has already answered. If n is not higher, it ignores the message. If n is higher, it makes a promise: it will refuse any future proposal numbered below n.
3. Along with that promise, the acceptor reports back the value it has already accepted, if any — and the number that value came in under. If it has accepted nothing, it says so.
4. If a majority of acceptors promise, the proposer has won the right to move to Phase 2. If it doesn't hear back from a majority, it gives up, picks an even higher number, and tries again.

Two things just happened, and both matter. The promise is a commitment to the future: an acceptor that promised for number n has slammed the door on every proposal numbered below n. The report is a window into the past: the proposer now knows what values, if any, are already floating around in the system. Phase 2 uses both.

Phase 2: accept and accepted#

Now the proposer names a value. But here is the rule that everything hinges on — it does not always get to name its own value.

1. The proposer looks at the reports it collected in Phase 1. If any acceptor reported an already-accepted value, the proposer must take the value that came with the highest proposal number and propose that — dropping its own value. Only if every acceptor reported 'accepted nothing' is the proposer free to propose the value it actually wanted.
2. It sends an accept(n, value) message to the acceptors, carrying the same number n from Phase 1 and the value it just settled on.
3. An acceptor that receives accept(n, value) accepts it — unless, in the meantime, it has promised for a number higher than n. If it has, it ignores the message; its newer promise wins. Otherwise it records the value and reports 'accepted'.
4. Once a majority of acceptors have accepted the same (n, value), that value is chosen. It is now the decision, forever. Learners are told, and the system moves on.

Walk our example through it, because the payoff is in the details. Proposer P (for set x = 5) runs Phase 1 with number 1, gets promises from all three acceptors, and sends accept(1, x = 5). But only acceptor A1 receives it before the network hiccups — one acceptor, not a majority. So x = 5 is accepted by A1 but not yet chosen.

Now proposer Q (for set x = 8) runs Phase 1 with number 2. A1 promises and reports 'I already accepted x = 5 under number 1'; A2 and A3 promise and report nothing. Q has a majority of promises, so it may proceed — but the rule bites. One acceptor reported an accepted value, so Q must propose that value, not its own. Q sends accept(2, x = 5), abandoning x = 8. All three accept, and x = 5 is chosen. Q wanted x = 8 and was forced to help x = 5 win instead.

The one rule that keeps a decision safe#

Why must a proposer adopt an already-accepted value instead of pushing its own? Because it cannot tell whether that value has already been chosen. In the example, when Q saw that A1 had accepted x = 5, Q had no way to know if x = 5 had quietly reached a majority somewhere and become the final decision. If it had, and Q proposed x = 8 anyway and got it accepted by a majority, the system would now hold two different chosen values — the exact disaster consensus must prevent.

The adopt-the-highest rule closes that gap. Any proposal that comes after a value could have been chosen is forced to carry that same value forward. So once a value reaches a majority, every later proposal proposes it too, and no competing value can ever slip through. This is the heart of Paxos. The prepare/promise dance and the proposal numbers exist for one purpose: to make sure a new proposer always sees any value that might already have won, and is compelled to keep it alive.

From one value to a log: Multi-Paxos#

Everything so far decides one value — a single slot. This is called single-decree Paxos, one decree, one decision. But a real system doesn't want to agree on one value; it wants to agree on an ordered stream of them: command 1, then command 2, then command 3 — a replicated log, the same thing /raft builds. Replay that agreed log on every server and they all end up identical.

The obvious approach is to run a separate instance of single-decree Paxos for each slot in the log. That works and it's correct, but it's wasteful: every slot pays for its own Phase 1, a full round-trip just to claim the right to propose, before it can even name a value.

Multi-Paxos removes that waste. The insight is that Phase 1 doesn't mention any particular value — it just claims proposing rights using a number. So one proposer runs Phase 1 once, for all future slots at the same time, and becomes the stable leader. After that, for each new command it only runs Phase 2: send accept, wait for a majority, done. One round-trip per command instead of two. The expensive prepare phase happens only when leadership changes.

What it costs#

Paxos buys safety with round-trips and messages, and the bill is easy to read once you know the two phases.

• Latency, single-decree: two round-trips to a majority — one for prepare/promise, one for accept/accepted. Each round-trip finishes as soon as the fastest majority of acceptors reply, so the slowest acceptor never gates you — only the ones you needed to form a majority.
• Latency, Multi-Paxos steady state: one round-trip per command. The leader already holds proposing rights, so each command needs only Phase 2. This is the number that matters in practice — the two-round cost is paid once per leadership, not per command.
• Fault tolerance: a group of 2f+1 acceptors tolerates f failures and still has a majority of f+1 alive. Three acceptors survive one failure; five survive two. Even sizes buy nothing — four acceptors still need a majority of three and tolerate only one failure — so groups are almost always 3 or 5.
• Messages: each phase is on the order of N messages out and N back, linear in the group size. Consensus groups stay small (3 or 5) for exactly this reason; you scale data by running many independent groups, not one huge group.