Paxos Algorithm
Paxos is a family of protocols for achieving consensus among a group of unreliable or failure-prone nodes in a distributed system, first formally described by Leslie Lamport and widely regarded as the foundational algorithm in distributed…
Definition
Paxos is a family of protocols for achieving consensus among a group of unreliable or failure-prone nodes in a distributed system, first formally described by Leslie Lamport and widely regarded as the foundational algorithm in distributed consensus theory.
Overview
Paxos addresses the same fundamental problem as later algorithms like Raft Consensus: letting a cluster of nodes agree on a single value even when some nodes crash or messages are lost or delayed. Leslie Lamport formalized Paxos in a paper in the late 1980s (published in 1998), and it became the theoretical foundation that much of modern Consensus Algorithm research builds upon. The protocol works through a series of numbered proposal rounds involving three logical roles — proposers, acceptors, and learners (a single node can play multiple roles). A proposer suggests a value with an associated round number; acceptors promise not to accept any earlier-numbered proposal and, if a majority of acceptors agree, the value becomes chosen. This majority-based quorum requirement is what allows Paxos to tolerate the failure of a minority of nodes while still making safe progress. Despite its theoretical importance and widespread influence, Paxos has a well-earned reputation for being difficult to fully understand and especially hard to implement correctly in production systems, largely due to the complexity of handling multiple concurrent proposers and edge cases in real deployments (a challenge Lamport himself acknowledged, later publishing a simplified explanation called 'Paxos Made Simple'). This difficulty was the direct motivation behind the creation of Raft, which achieves equivalent safety guarantees with a more approachable structure. Paxos variants still power some production systems, including Google's Chubby lock service and parts of Google Spanner, and remain a core topic in Distributed Systems education even where newer algorithms are used in practice.
Key Concepts
- Foundational algorithm in distributed consensus theory
- Formalized by Leslie Lamport in the late 1980s
- Uses proposer, acceptor, and learner roles in numbered rounds
- Requires a majority quorum of acceptors to choose a value
- Tolerates failure of a minority of participating nodes
- Notoriously difficult to implement correctly in practice
- Directly inspired the design of the more approachable Raft algorithm