The Paxos Consensus Protocol: How Distributed Systems Agree on One Value

The Problem: Agreement Under Unreliable Conditions

At the heart of distributed computing lies a stubborn challenge: how do multiple independent machines, connected by an imperfect network, settle on exactly one value when any of them might crash or any message might vanish without warning? This is the distributed consensus problem, and it matters enormously in practice. Databases need to agree on the order of transactions, lock services need to agree on who holds a lock, and replicated logs need every replica to agree on the same sequence of commands. Naive approaches, like picking a single coordinator and trusting it completely, fall apart the moment that coordinator crashes or becomes unreachable. A correct consensus protocol must tolerate node failures and network delays while still guaranteeing two properties: safety, meaning the system never agrees on two different values, and liveness, meaning it eventually agrees on something as long as enough of the system is working. Paxos was the first protocol proven to solve this rigorously, and its core insight is that agreement does not require every node to respond, only a majority. That single idea, that overlapping majorities always share at least one common member, is what makes the whole system hang together even when parts of it are unreachable or slow.

Meet the Cast: Proposers, Acceptors, and Learners

Paxos assigns every participating node one or more of three roles. A proposer is the node that wants to get a value accepted, for example a client request to write a new entry to a replicated log. An acceptor is a node that votes on proposals; acceptors form the durable memory of the system and must persist their promises even across restarts. A learner is a node that simply wants to find out which value was ultimately chosen, without participating in the voting itself. In real deployments a single physical server often plays multiple roles at once, acting as both proposer and acceptor. The separation of roles is what makes Paxos so flexible: any node can attempt to propose a value at any time, multiple proposers can compete simultaneously, and the protocol still converges on one winner. Acceptors never coordinate directly with each other; they only respond to proposers, which keeps the communication pattern simple and avoids the need for a fragile, always-on leader. This design also means the system degrades gracefully. If a proposer crashes mid-round, another proposer can simply start a new round with a higher proposal number and pick up where things left off, without corrupting anything the acceptors have already recorded.

Phase 1: Prepare and Promise

Every Paxos round begins with a uniquely numbered proposal, and these monotonically increasing proposal numbers are the mechanism that resolves conflicts between competing proposers. In Phase 1, a proposer picks a proposal number n higher than any it has used before and sends a prepare request bearing that number to a majority of acceptors. Each acceptor that receives the request compares n against the highest-numbered proposal it has already promised to honor. If n is higher, the acceptor promises never to accept any future proposal numbered lower than n, and it replies with that promise, along with the value of the highest-numbered proposal it has already accepted, if any. If n is not higher, the acceptor simply ignores or rejects the request. This phase is essentially reconnaissance: the proposer is checking whether the coast is clear and, crucially, discovering whether some earlier proposal might already have been accepted by part of the majority. That discovery step is what prevents Paxos from silently overwriting a value that another proposer already got partially accepted. Only once a proposer has heard promises back from a majority of acceptors does it have enough information to safely move on to actually proposing a value in Phase 2.

Phase 2: Accept and Accepted

Armed with a majority of promises, the proposer enters Phase 2. It must choose the value to propose carefully: if any acceptor in Phase 1 reported an already-accepted value, the proposer is obligated to adopt the value from the highest-numbered such report rather than substitute its own. This rule is the safety linchpin of Paxos, ensuring that a value already on its way to being chosen cannot be silently replaced. The proposer then sends an accept request, containing its proposal number n and the chosen value, to that same majority of acceptors. Each acceptor accepts the request and records the value, unless it has since promised, in response to a higher-numbered prepare from a different proposer, to ignore proposals numbered n or lower. If the proposer receives acceptance from a majority of acceptors, the value is officially chosen, though other nodes may not know it yet. Learners then find out about the chosen value either by acceptors notifying them directly or through a distinguished learner that aggregates and broadcasts the result. Because a value only becomes chosen once a full majority has accepted it, and because any two majorities always overlap, it is mathematically impossible for two different values to both reach majority acceptance.

Why Majority Quorums Guarantee Safety, and Paxos in the Real World

The reason a majority quorum is so powerful comes down to simple set overlap: with any group of nodes, two subsets that each contain more than half the members are guaranteed to share at least one node in common. That shared node has seen both rounds and enforces consistency between them, because it will not accept a lower-numbered proposal after promising to honor a higher one. This property holds even during a network partition, since at most one side of a split network can contain a majority, so only one side can possibly make progress, while the minority side simply stalls until connectivity is restored. This tradeoff, favoring safety over availability during a partition, is exactly what the CAP theorem predicts for consistent systems. Paxos's ideas proved so foundational that they shaped decades of infrastructure. Google's Chubby lock service, described in a widely read 2006 paper, used a Paxos-based replicated log to keep its lock and configuration data consistent across data centers, and Chubby in turn inspired ZooKeeper. More recently, the Raft consensus algorithm was explicitly designed as a more understandable alternative to Paxos, and systems like etcd, which powers Kubernetes, are built on Raft. Despite the different packaging, Raft's leader election and log replication mechanisms trace their intellectual lineage directly back to Paxos, making it fair to call Paxos the ancestor of the entire modern consensus family.

Frequently asked questions

Try it live

Everything above runs in your browser — open The Paxos Consensus Protocol: How Distributed Systems Agree on One Value and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.