Paxos Primer
Paxos is the canonical consensus protocol for asynchronous distributed systems. It lets a cluster of unreliable nodes agree on a single value even when messages drop, processes crash, and clocks drift. This primer walks through the three roles, the two-phase message flow, and the safety invariants that make Paxos tolerant to minority failures without ever producing a split decision.
1.Roles and the Quorum
Every node plays one or more of three roles: proposers initiate values, acceptors vote on proposals, and learners observe decisions. A quorum is any majority of acceptors. Because any two majorities intersect in at least one node, the intersection acceptor enforces consistency across rounds and prevents two conflicting values from ever being chosen.
- Proposer drives a ballot with a monotonic number.
- Acceptor persists its highest promise and accepted value.
- Learner replicates the chosen value to client state.
2.The Two-Phase Protocol
Phase 1 is Prepare/Promise: a proposer picks a ballot number n and asks a quorum to promise not to accept anything lower. Phase 2 is Accept/Accepted: the proposer issues an accept message carrying either its own value or the highest-numbered value any acceptor already promised. Once a majority accepts, the value is chosen and the decision is irrevocable.
// Phase 1
proposer -> acceptors: PREPARE(n)
acceptor -> proposer: PROMISE(n, prevAccepted?)
// Phase 2
proposer -> acceptors: ACCEPT(n, value)
acceptor -> proposer: ACCEPTED(n, value)
// Decision
if |ACCEPTED| > |acceptors| / 2:
learners.commit(value)3.Safety and Liveness Trade-offs
Paxos guarantees safety unconditionally: at most one value is ever chosen for a given instance. Liveness, however, requires a single distinguished proposer; competing proposers can livelock by perpetually outbidding each other. Practical deployments solve this with a leader election layer (Multi-Paxos, Raft) that pins one proposer for a stable term, reducing the steady-state cost to a single round trip per decision.