Paxos Algorithm

Paxos is the foundational consensus protocol for crash-fault-tolerant distributed systems, introduced by Leslie Lamport in 1989. It solves the problem of how a group of distributed nodes can agree on a single value when some nodes may fail silently, using a two-phase commit mechanism with proposers, acceptors, and learners. Despite its notorious reputation for impenetrability — Lamport himself noted that it was "as simple to understand as two-phase commit" though few engineers agreed — Paxos underlies nearly every production distributed coordination service, often in disguised form through protocols like Raft that preserve its core logic while sacrificing some edge-case guarantees for clarity.

The protocol's central insight is that agreement requires only a quorum of acceptors, not unanimous consent. A proposer sends a prepare request with a unique proposal number; acceptors promise not to accept lower-numbered proposals; the proposer then requests acceptance of its value. If a majority quorum responds at each phase, agreement is reached even if minority partitions occur. This is structural causation in miniature: the consensus emerges from the quorum topology, not from any individual node's authority.

The deeper significance of Paxos is that it proves consensus is achievable in asynchronous systems with crash failures — the positive result that makes the FLP impossibility so devastating by contrast. Where FLP shows what cannot be done with even one faulty process in full asynchrony, Paxos shows what can be done when failures are limited to crash-stop. The gap between these two results — between the impossibility and the possibility — is the design space of practical consensus.