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
Use Cases
Frequently Asked Questions
From the Blog
Feature Engineering: Turning Data Into Signal
Feature engineering turns raw columns into inputs a model can actually learn from. Learn the core techniques that often matter more than the algorithm itself.
Read More ProgrammingWhat Is Big O Notation? A Beginner Guide
Big O notation describes how an algorithm's time or memory grows as input size increases. Learn the common complexities and how to analyze your own code.
Read More Data ScienceWhat Is Feature Engineering in Machine Learning?
Feature engineering is transforming raw data into inputs that help models learn. Good features often matter more than the algorithm. Learn the core techniques here.
Read More AI & TechnologyWhat Is Gradient Descent Explained for Beginners
Gradient descent is the algorithm that trains most machine learning models by repeatedly nudging parameters in the direction that reduces error, step by step.
Read More