The Grandfather of Consensus
Paxos is the original consensus algorithm, first described by Leslie Lamport in 1989 (published 1998). It is mathematically proven to be correct and is the theoretical foundation for much of the distributed systems field. Google's Chubby lock service and Spanner database are built on Paxos variants.
Paxos is famous for two things:
1. Its correctness: It guarantees that a distributed system will never commit two conflicting values (safety), even under arbitrary message delays and node failures.
2. Its complexity: It is notoriously difficult to understand and even harder to implement correctly. Lamport himself wrote a follow-up paper titled "Paxos Made Simple" because the original was so opaque.
How Basic Paxos Works
Basic Paxos reaches consensus on a single value through two phases involving two roles: Proposers (nodes that want to propose a value) and Acceptors (nodes that vote on proposals).
Phase 1 — Prepare:
A Proposer picks a unique proposal number n and sends a Prepare(n) message to a quorum of Acceptors. Each Acceptor responds with a promise: "I will not accept any proposal numbered less than n." If the Acceptor has already accepted a value, it includes that value in its response.
Phase 2 — Accept:
If the Proposer receives promises from a quorum, it sends an Accept(n, v) message. The value v is either the highest-numbered value returned by any Acceptor in Phase 1 (if any existed), or the Proposer's own desired value. Acceptors accept this proposal unless they have already promised a higher number.
Once a quorum of Acceptors accepts the same proposal number, the value is chosen (committed).
Multi-Paxos
Basic Paxos is expensive — two round trips per value. Multi-Paxos optimizes this by electing a stable Leader (called the Distinguished Proposer). Once a leader is established, Phase 1 is skipped for subsequent proposals, reducing the cost to a single round trip per log entry. This is the variant used in production systems.
Because of its steep learning curve and the many subtle implementation details (leader leases, log compaction, membership changes), many modern systems use Raft instead.