If the FLP theorem established the impossibility of guaranteed consensus in asynchronous networks, Leslie Lamport’s Paxos protocol demonstrated how to achieve consensus with provable, unbreakable safety in practice. First circulated in 1990 under the allegorical guise of an ancient Aegean parliamentary system (“The Part-Time Parliament”), Paxos remains the intellectual bedrock upon which modern planetary infrastructure—from Google Chubby and Spanner to Apache ZooKeeper—is engineered.
1. The Architectural Roles of Paxos
In the Classic Single-Decree Paxos (Synod) protocol, nodes assume three conceptual roles (though a single physical server typically executes all three):
- Proposers: Advocate client values by issuing proposal numbers $n$ and attempting to guide the cluster toward a unanimous decree.
- Acceptors: Form the consensus memory. They store promises and accepted values, acting as intersecting quorums to preserve agreement invariants.
- Learners: Passive observers that read the outcome once an entry has been accepted by a majority quorum of Acceptors.
2. The Two Phases of the Synod Protocol
To safely choose a single value $v$, Paxos executes two distinct phases across a cluster of $2F + 1$ Acceptors:
Phase 1: Prepare & Promise (Acquiring Leadership & Learning History)
- Phase 1a (Prepare): A Proposer chooses a globally unique, monotonically increasing proposal number $n in mathbb{N}$ (structured as $langle text{counter}, text{node_id} rangle$) and broadcasts $text{Prepare}(n)$ to a majority quorum of Acceptors.
- Phase 1b (Promise): When an Acceptor receives $text{Prepare}(n)$:
- If $n > n_{text{promised}}$, the Acceptor updates its internal state: $n_{text{promised}} leftarrow n$.
- It responds with a $text{Promise}(n, v_{text{max}}, n_{text{max}})$, promising never to accept any future proposals numbered less than $n$, and returning the highest-numbered proposal it has already accepted (if any).
- If $n le n_{text{promised}}$, the request is rejected or ignored.
Phase 2: Accept & Accepted (Committing the Value)
- Phase 2a (Accept Request): If the Proposer receives promises from a majority quorum of Acceptors, it selects value $v$:
- If any Acceptor returned a previously accepted value in Phase 1b, the Proposer must set $v$ to the value associated with the highest $n_{text{max}}$ among all received promises.
- If no Acceptor had previously accepted a value, the Proposer is free to propose its own client value $v$.
- The Proposer broadcasts $text{Accept}(n, v)$ to the Acceptors.
- Phase 2b (Accepted): When an Acceptor receives $text{Accept}(n, v)$, it accepts the proposal if and only if:
$$n ge n_{text{promised}}$$
Upon accepting, it updates its state ($n_{text{max}} leftarrow n$, $v_{text{max}} leftarrow v$) and notifies the Proposer and Learners.
3. Mathematical Proof of Safety: Invariant $P2^c$
The safety of Paxos hinges entirely on the Pigeonhole Principle governing intersecting majorities. Let $Q_1$ be the majority quorum of Acceptors that promised proposal $n_1$, and let $Q_2$ be the majority quorum that accepted proposal $n_2$. Because any two majorities of size $lfloor N/2 rfloor + 1$ must overlap:
$$|Q_1 cap Q_2| ge 1$$
Lamport formulated the core inductive safety property $P2^c$:
$$text{For any } v text{ and } n, text{ if a proposal } (n, v) text{ has been issued, then there is a quorum } Q text{ such that either:}$$
$$text{(a) No acceptor in } Q text{ has accepted any proposal numbered less than } n, text{ or}$$
$$text{(b) } v text{ is the value of the highest-numbered proposal among all proposals } < n text{ accepted by any member of } Q.$$
Because any subsequent Proposer $n^prime > n$ must receive promises from a majority quorum, its quorum must intersect with at least one Acceptor that already accepted $(n, v)$. That Acceptor reports $(n, v)$ in Phase 1b, forcing the new Proposer to adopt $v$. Once a value is chosen by a majority, it can never be overturned.
4. Livelock & Dueling Proposers
While Paxos guarantees absolute safety, it is vulnerable to livelock under unconstrained concurrency. If Proposer $P_1$ prepares $n_1$, and before it can issue Phase 2a, Proposer $P_2$ prepares $n_2 > n_1$, Acceptors will reject $P_1$’s Accept request. $P_1$ then immediately retaliates by preparing $n_3 > n_2$, creating an infinite duel where no proposal ever completes Phase 2.
5. Multi-Paxos: Production State Machine Replication
Running the two-phase Synod protocol for every single database log entry would double network round-trips and invite continuous duels. In production, systems deploy Multi-Paxos:
- Amortized Phase 1: A stable leader executes Phase 1 once for the entire future of its term.
- Single-RTT Steady State: For subsequent log entries, the leader executes only Phase 2 (one round trip to commit).
- Leader Leases: The leader maintains a synchronized time-bounded lease. As long as heartbeats are acknowledged by a majority, the leader serves linearizable reads locally without cross-node network coordination.
