Paxos

Why it matters

Paxos is the proof that consensus is achievable with crash failures and an asynchronous network, and every production consensus system is either Paxos, a Paxos variant, or Raft, which was designed as a more teachable Paxos. Interviewers rarely ask you to implement it; they ask whether you understand the one idea that makes it safe, because that idea recurs in every coordination protocol: a proposer must learn what may already have been decided before proposing anything new.

The idea

Paxos has three roles, usually all played by every node: proposers suggest values, acceptors vote, learners find out what was decided. Agreement on a single value proceeds in two phases, each needing a majority of acceptors. Every proposal carries a unique, increasing ballot number (a counter plus the proposer's id).

1. 1

   Phase 1a: prepare

   A proposer picks a ballot n higher than any it has used and sends prepare(n) to the acceptors.
2. 2

   Phase 1b: promise

   An acceptor that has not promised a ballot higher than n replies promise(n), including the highest-ballot value it has previously accepted, if any, and commits to ignore any proposal with a ballot below n.
3. 3

   Phase 2a: accept

   Once the proposer has promises from a majority, it must propose the value from the highest-ballot accepted value among the promises, if any acceptor reported one; only if none did may it propose its own value. It sends accept(n, value).
4. 4

   Phase 2b: accepted

   An acceptor that has not promised a higher ballot accepts and records (n, value), and tells the learners. When a majority has accepted the same ballot, the value is decided.

Why the adoption rule keeps it safe

Suppose value x was accepted by a majority at ballot 5 (so it is decided, even if nobody has learned it yet). Any later proposer at ballot 7 collects promises from a majority, which must overlap the earlier majority in at least one acceptor, and that acceptor reports (5, x). The rule forces the proposer to propose x again. So once a value could have been decided, every subsequent ballot can only re-propose it: no second value can ever be decided. That is agreement, and it holds regardless of crashes, delays or how many proposers compete.

Liveness and duelling proposers

Two proposers can keep outbidding each other with higher ballots so that neither completes phase 2: a livelock. Paxos sidesteps it with randomized backoff or by electing a distinguished proposer. Nothing unsafe happens during the duel; the system simply does not decide, which is FLP's unavoidable price.

Multi-Paxos: a stable leader

Running both phases for every log slot is slow. Multi-Paxos elects a leader that runs phase 1 once for an entire range of slots and then runs only phase 2 (one round trip) per command. The leader proposes commands in order into successive slots; followers accept; a majority acceptance commits. When the leader fails, a new one runs phase 1 again, discovering any slots with possibly-decided values and re-proposing them. This is the shape of every production system described as "Paxos-based": Chubby, Spanner's per-group Paxos, Megastore.

Why Raft exists

Paxos's published form is a single-value protocol plus a sketch of Multi-Paxos; the parts that matter in production (leader election, log compaction, membership change) were left as exercises, and teams built subtly different and sometimes incorrect systems. Raft, next lesson, is Multi-Paxos reorganised around a strong leader with a contiguous log and fully specified mechanics, which is why most new systems choose it. Conceptually they are equivalent: both achieve consensus with majorities and the rule that a new leader must learn what may already have been decided.