Paxos Consensus Protocol
Paxos is a family of consensus protocols that enable a group of unreliable nodes to agree on a single value, even when some nodes fail or messages are lost, as long as a majority of nodes are operational.
What It Really Means
Distributed systems need agreement. Which node is the leader? What is the committed order of transactions? What is the current cluster configuration? Paxos answers these questions with provable guarantees: once a value is chosen by a majority, no different value can ever be chosen, even if nodes crash and restart.
Leslie Lamport published the Paxos algorithm in 1998 (originally written in 1989) using the metaphor of a Greek parliament on the island of Paxos. The paper was famously difficult to understand — Lamport later published "Paxos Made Simple" in 2001, noting that the algorithm itself is simple but reasoning about distributed systems is inherently complex.
Paxos is the theoretical foundation behind Google's Chubby lock service (which underpins Bigtable, Megastore, and Spanner), Apache ZooKeeper's ZAB protocol (a Paxos variant), and many internal systems at large tech companies. While Raft has become more popular for new implementations due to its clarity, understanding Paxos remains essential for distributed systems interviews and for understanding the theory behind modern consensus.
How It Works in Practice
The Three Roles
- Proposer: Proposes values and drives the protocol forward
- Acceptor: Votes on proposals and stores accepted values (the "memory" of the protocol)
- Learner: Learns the chosen value once consensus is reached
In practice, a single node often plays all three roles simultaneously.
Basic Paxos (Single-Value Consensus)
Phase 1: Prepare
- A proposer selects a unique proposal number
n (higher than any it has seen)
- It sends a
Prepare(n) message to a majority of acceptors
- Each acceptor responds with a
Promise(n): it promises not to accept any proposal with a number less than n, and returns any value it has previously accepted
Phase 2: Accept
4. If the proposer receives promises from a majority, it sends Accept(n, v) where v is either the value from the highest-numbered previously accepted proposal (if any) or the proposer's own value
5. Each acceptor receives the Accept request and accepts it unless it has already promised a higher proposal number
6. Once a majority of acceptors have accepted, the value is chosen
Key insight: In Phase 2, if any acceptor already accepted a value, the proposer must use that value (not its own). This is what prevents conflicting values from being chosen — it forces convergence.
Multi-Paxos (Sequence of Values)
Basic Paxos agrees on a single value. Real systems need to agree on a sequence of values (a log). Multi-Paxos runs a separate Paxos instance for each log position but optimizes by electing a stable leader who skips Phase 1 for subsequent proposals. This is essentially what Raft formalized into a cleaner protocol.
Real-World: Google Chubby
Chubby is Google's distributed lock service, built on Multi-Paxos. It provides coarse-grained locks, leader election, and a small amount of reliable storage. Google's Bigtable uses Chubby to elect tablet server leaders. Spanner uses Paxos groups for replication within each shard.
Chubby runs with 5 replicas (tolerating 2 failures). A stable leader handles most operations without running full Paxos rounds, making it fast in the common case. The full protocol only runs during leader changes.