The Paxos Algorithm Explained
The Paxos algorithm, developed by Leslie Lamport in the late 1980s and published in 1998, is one of the most important and famously difficult to understand algorithms in distributed systems. It provides a way for a distributed system to reach consensus on a value, even in the presence of failures. Despite its complexity, Paxos forms the theoretical foundation for many production consensus systems including Google's Chubby lock service and the underlying consensus in Google's Spanner database.
Roles in the Paxos Protocol
Paxos involves three distinct roles that nodes can play: the Proposer, the Acceptor, and the Learner. A Proposer suggests a value for the system to agree upon. Acceptors form the quorum and vote on proposed values. Learners receive the final agreed-upon value once consensus is reached. A single physical node can play multiple roles simultaneously, and in practice, this is often how systems are designed for efficiency.
The protocol operates in two phases. In the Prepare phase, a Proposer sends a Prepare request with a proposal number to a majority of Acceptors. Acceptors respond with a promise not to accept proposals with lower numbers, and they report any previously accepted values. In the Accept phase, if the Proposer receives promises from a majority, it sends an Accept request with the value to those Acceptors. Acceptors accept the value unless they have already promised to ignore proposals with that number.
Why Paxos is Hard to Understand
Lamport himself famously noted that Paxos is among the most difficult algorithms to understand, primarily because of its subtle invariants and the many edge cases it must handle. The algorithm must work correctly even with arbitrary message delays, node failures, and network partitions. Furthermore, the seemingly simple requirements translate into a non-trivial state machine that requires careful reasoning to verify.
To make Paxos more accessible, Lamport later published "Paxos Made Simple" in 2001, which used a fictional parliamentary analogy to explain the algorithm. While this paper helped some readers, many still find the original formulation challenging. Alternative explanations and visualizations have proliferated, each attempting to shed light on different aspects of the protocol.
From Paxos to Raft
Recognizing the difficulty of teaching Paxos, Diego Ongaro and John Ousterhout developed the Raft consensus algorithm in 2013. Raft was designed from the ground up to be understandable while providing equivalent guarantees to Paxos. The key insight of Raft is to decompose consensus into three relatively independent subproblems: leader election, log replication, and safety.
Raft maintains a strong leader model, where all client requests are routed through a single elected leader. This simplifies the algorithm significantly compared to Paxos, where any node can be a Proposer. The leader replicates log entries to followers and considers an entry committed once it is stored on a majority of nodes. Raft's deterministic leader election with randomized timeouts provides a practical alternative to Paxos and has been widely adopted in production systems.
Conclusion
Both Paxos and Raft have proven their worth in production systems, with each offering different tradeoffs. Paxos provides the theoretical foundation and has been battle-tested in some of the largest distributed systems in the world. Raft offers better understandability and has become the algorithm of choice for many new systems. Understanding both provides valuable insight into the fundamental challenges of distributed consensus.
As distributed systems continue to evolve, these algorithms remain at the core of reliable coordination. Whether you are building a new database, a coordination service, or a distributed lock manager, the principles underlying Paxos and Raft will guide your design decisions for years to come.