Paxos is a family of protocols for solving consensus in a network of unreliable processors. Developed by Leslie Lamport, it became the foundation for building reliable distributed systems and influenced virtually all modern consensus algorithms.
The Consensus Problem
How can a group of computers agree on a single value when messages can be lost or delayed, and some computers might fail? This problem is fundamental to distributed systems—from database replication to distributed locks.
The Algorithm
Paxos uses a sequence of proposals and acceptances:
- Prepare: A proposer sends a proposal number to acceptors
- Promise: Acceptors promise not to accept older proposals
- Accept: The proposer asks acceptors to accept a value
- Learn: Once a majority accepts, the value is chosen
Presentation and Reception
Lamport first wrote about Paxos in 1989 using an allegory about a fictional Greek island parliament. The paper was considered too whimsical and wasn’t published until 1998. A more straightforward explanation, “Paxos Made Simple,” followed in 2001.
Impact
Paxos and its variants underpin modern distributed systems: Google’s Chubby and Spanner, Apache ZooKeeper, and countless other systems use Paxos-derived protocols. The Raft consensus algorithm was designed as a more understandable alternative to Paxos.