We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningAdvanced · Distributed Systems Core
A family of protocols for solving consensus in unreliable networks. Famously difficult to understand but mathematically proven correct.
In short
Paxos is a family of distributed consensus protocols that lets a group of machines agree on a single value even when some of them crash, restart, or have messages delayed or lost. It guarantees safety (the group never agrees on two different values) under crashes, restarts, lost or delayed messages, and network partitions alike, and reaches a decision once a majority of nodes can talk to each other.
In short
Paxos is a family of distributed consensus protocols that lets a group of machines agree on a single value even when some of them crash, restart, or have messages delayed or lost. It guarantees safety (the group never agrees on two different values) under crashes, restarts, lost or delayed messages, and network partitions alike, and reaches a decision once a majority of nodes can talk to each other.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Paxos across a run of lessons, not one page. These 4 alone are about 103 minutes of step-by-step reading, 2 of them with code you run in the browser, all with a quiz.
Paxos, Raft, and ZAB, how distributed nodes agree on a single value despite failures.
Schedule messages for future delivery, process them later, not now.
When nodes can't talk to each other, the failure mode that defines distributed systems.
Model system behavior as a finite set of states and transitions, the foundation of distributed protocols.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Consensus Algorithmspay once,
yours for life
Imagine five servers that all need to agree on one fact, like which transaction commits first or who holds a lock. Some servers might be slow, some might crash mid-decision, and messages between them can arrive late, out of order, or not at all. Paxos is the protocol that gets these servers to agree on exactly one value and never change their minds, no matter how badly the network misbehaves.
The core promise is safety: two different servers will never believe two different values were chosen. The protocol gives up on liveness in the worst case, meaning it can stall during chaos, but it will never produce a wrong answer. This split matters because in distributed systems a slow answer is recoverable but a contradictory answer corrupts data permanently.
Paxos was published by Leslie Lamport in 1998 as The Part-Time Parliament, and again more plainly in 2001 as Paxos Made Simple. It is the theoretical foundation under most strongly consistent systems built since, even when those systems use a friendlier variant on top.
Each node plays one or more roles. Proposers suggest values, acceptors vote on them, and learners observe the final outcome. A single round of agreement on one value is called Basic Paxos, and it runs in two phases.
In Phase 1, a proposer picks a unique, increasing proposal number n and sends a prepare(n) message to the acceptors. Each acceptor that has not already seen a higher number promises not to accept anything numbered below n, and reports back any value it previously accepted. Once a proposer hears promises from a majority, it moves on.
In Phase 2, the proposer sends accept(n, value). The critical rule: if any acceptor already reported an accepted value in Phase 1, the proposer must reuse the value tied to the highest proposal number it heard about, not its own. This is what prevents two values from ever winning. When a majority of acceptors accept, the value is chosen and learners are told.
Because a value is chosen by a majority, any future majority must overlap in at least one acceptor that remembers it. That overlap is the whole trick. Running a fresh two-phase round for every single decision is expensive, so Multi-Paxos elects a stable leader that skips Phase 1 for a stream of decisions, getting you down to one round trip per value in the common case.
Reach for Paxos-style consensus when you need a small group of nodes to agree with strong consistency: leader election, distributed locks, replicating a config or metadata store, or ordering writes to a state machine. It needs a majority (a quorum) to make progress, so a 3-node cluster tolerates 1 failure and a 5-node cluster tolerates 2.
The biggest cost is not throughput, it is comprehension and correctness of implementation. Lamport's papers describe Basic Paxos clearly but leave the practical machinery (log compaction, membership changes, leader handoff) as an exercise, and teams have shipped subtly broken versions for years. Google engineers documented this pain in the paper Paxos Made Live.
Latency is also a real factor. Every decision needs a round trip to a majority, so spreading nodes across distant regions adds tens to hundreds of milliseconds per commit. This is why most consensus clusters keep an odd, small node count in one or a few nearby zones. If you find Paxos hard to reason about, Raft was designed in 2014 to be an equivalent but more understandable alternative, and most new systems now choose Raft for that reason.
Google's Chubby lock service is the textbook case. Chubby runs a cell of five replicas, uses Multi-Paxos to keep their logs identical, and elects one as the master. Services like Bigtable and the Google File System rely on Chubby to elect their own leaders and store small bits of critical metadata, so a single Paxos cluster quietly backstops much of Google's infrastructure.
When the Chubby master crashes, the remaining replicas run a Paxos round to agree on a new master and on exactly where the log left off. Clients see a brief pause of a few seconds, then service resumes with no lost or duplicated decisions. That pause is the liveness cost being paid so that safety is never violated, which is precisely the bargain Paxos was designed to make.
Google Chubby and Spanner
Chubby uses Multi-Paxos across five replicas for locks and leader election; Spanner uses Paxos groups to replicate each shard across datacenters.
Apache ZooKeeper
Coordinates distributed systems with ZAB, a consensus protocol in the Paxos family, used by Kafka, HBase, and Hadoop for leader election and config.
Microsoft Azure Storage
Uses a Paxos-based stream layer to keep replicas of stored data consistent across nodes within a storage stamp.
Amazon DynamoDB
Uses Paxos-derived consensus internally to agree on the leader of each partition's replication group before serving strongly consistent reads and writes.
Both solve the same problem of consensus and tolerate the same failures, but Raft was designed to be easier to understand and implement. Raft makes the leader central and explicit and keeps the replicated log in clear order, while Paxos is described more abstractly and leaves many practical details to the implementer. Most new systems pick Raft for that reason, but they are functionally equivalent.
Lamport's original paper framed it as a fictional ancient parliament, and even his plainer follow-up describes only the single-decision case. The hard parts in practice, like running many decisions, electing and replacing leaders, compacting logs, and changing cluster membership, are mostly left out, so engineers have to fill in correct details that are easy to get subtly wrong.
You need at least a majority of nodes alive to make progress, so cluster sizes are usually odd. Three nodes tolerate one failure, five nodes tolerate two, and seven tolerate three. Odd sizes are preferred because adding an even node raises cost without improving fault tolerance.
No. Paxos never produces conflicting decisions. If the network splits so that no side has a majority, the protocol simply stops making new decisions until connectivity returns. It sacrifices availability during a partition rather than risk agreeing on two different values, consistent with the CAP theorem.
Basic Paxos agrees on one value and runs two message rounds to do it. Multi-Paxos optimizes for a continuous stream of decisions by electing a stable leader that can skip the first phase, so each new value usually takes a single round trip to a majority. Almost all real deployments use Multi-Paxos rather than Basic Paxos.
Raft
A consensus algorithm designed to be understandable. Uses leader election and log replication. Powers etcd (used by Kubernetes) and CockroachDB.
Consensus
The process of getting multiple nodes in a distributed system to agree on a single value. The foundation of distributed databases and coordination services.
Leader Election
The process of choosing one node in a cluster to coordinate actions. If the leader fails, a new one is elected. Used by Kafka, ZooKeeper, and etcd.
CAP Theorem
When a network failure splits a distributed data store, each node must either refuse requests to stay consistent or keep answering with possibly stale data. It cannot guarantee both during the partition.
CQRS
Command Query Responsibility Segregation: using different models for reading and writing data. Reads and writes have different performance needs, so separate them.
Event Sourcing
Storing every state change as an immutable event instead of just the current state. You can rebuild any past state by replaying events.
This page explains the idea. The "Consensus Algorithms" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Consensus Algorithms lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Paxos in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
