Paxos: the original consensus algorithm

Paxos solves the consensus problem from lesson 6 using nodes playing one of three roles (a single node can play more than one role at once in a real deployment):

Paxos runs in two phases, and the key insight is that phase one doesn't commit to a value yet — it only establishes the right to propose one:

Phase 1 (Prepare/Promise): A proposer picks a proposal number n (higher than any it's used before) and asks acceptors to promise not to accept any proposal numbered lower than n. If a majority of acceptors promise, the proposer can proceed — critically, an acceptor that already accepted an earlier proposal tells the proposer about it, which is the mechanism that prevents two different values from both getting chosen.

Phase 2 (Accept): The proposer sends an actual value to accept — either its own, or (if an acceptor reported an earlier accepted value in phase 1) that earlier value instead, to guarantee any value a majority already leaned toward doesn't get silently overwritten. If a majority of acceptors accept, that value is chosen — permanently, safely, regardless of what happens to any node afterward.

Any two majorities out of the same set of nodes must overlap by at least one node — this simple fact is the entire safety mechanism. If value A was chosen by one majority and a different proposer later tries to get value B chosen, at least one acceptor in B's majority already promised something tied to A's proposal number, and the protocol's rules force that proposer to propose A's value instead of B's. Two different values getting chosen independently is mathematically prevented by this overlap, not merely made unlikely.

The core two-phase idea above is genuinely simple — the difficulty comes from correctly handling every edge case in a real implementation: what happens with multiple competing proposers repeatedly outbidding each other (a real liveness risk called dueling proposers, where the protocol can theoretically stall without ever violating safety), how to actually run this repeatedly for a sequence of values instead of just one ("Multi-Paxos"), and how to handle cluster membership changing over time. The original 1998 paper describing all this was famously considered difficult even by experienced distributed-systems researchers — which is precisely the frustration that motivated Raft, covered next.