Paxos

Imagine you and four friends are trying to agree on where to eat dinner — but any of you might fall asleep mid-conversation, forget what was said, or repeat an old message that arrived late. How do you reach a decision that everyone who stays awake will honor?

This is, roughly, the consensus problem in distributed computing. A cluster of servers must agree on a single value — a database write, a leader election, the next command in a log — even though any server can crash and restart, and network messages can arrive late or out of order.

Paxos, invented by Leslie Lamport around 1989 and published formally in 1998 (with a simpler explanation in 2001 as "Paxos Made Simple"), was the first clean solution. It guarantees that:

1. Only one value is ever chosen.
2. Any chosen value was actually proposed by some node.
3. If a value is chosen, every node that asks will eventually learn it.

The catch? Even the inventors called it "surprisingly subtle." Paxos is proven correct, is widely deployed, and remains the yardstick every newer consensus protocol (Raft, Zab, Multi-Paxos) is measured against.

The demo below runs a simplified single-decree Paxos with 3 proposers and 5 acceptors. Each proposer picks a random proposal number and a value. Step through the two phases and watch the nodes converge on exactly one chosen value, even when some acceptors are slow or a proposer loses the race.

<div class="hint">{{hint}}</div>
<div id="grid"></div>
<div class="controls">
  <button id="btn-prepare" type="button">{{btn_prepare}}</button>
  <button id="btn-accept"  type="button" disabled>{{btn_accept}}</button>
  <button id="btn-reset"   type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a1a2e; font-size: 14px; }
.hint { font-size: .88rem; color: #555; margin-bottom: .6rem; line-height: 1.45; }

#grid { display: grid; grid-template-columns: 110px repeat(5, 1fr); gap: 4px; margin-bottom: .7rem; }
.gh { font-weight: 700; font-size: .78rem; text-align: center; padding: 4px 2px;
      background: #e8eef4; border-radius: 6px; display: flex; align-items: center; justify-content: center; }
.gh.row-h { justify-content: flex-start; padding-left: 8px; font-size: .8rem; }
.cell { border-radius: 6px; padding: 5px 4px; min-height: 44px; font-size: .75rem;
        display: flex; flex-direction: column; align-items: center; justify-content: center;
        text-align: center; border: 1px solid #d4dce6; background: #f5f7fa; gap: 2px; }
.cell .label { font-size: .65rem; color: #778; line-height: 1; }
.cell .val   { font-weight: 700; font-size: .85rem; }
.cell.promised { background: #e0f0ff; border-color: #6ab0e8; }
.cell.accepted  { background: #d4f5d4; border-color: #4caf77; }
.cell.rejected  { background: #fde8e8; border-color: #e07070; }
.cell.idle      { background: #f5f7fa; }

.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

#log { max-height: 130px; overflow-y: auto; font-size: .78rem; line-height: 1.7;
       background: #f9fafb; border: 1px solid #dde3ea; border-radius: 8px; padding: .4rem .6rem; }
.log-prepare { color: #1a6fb5; }
.log-accept  { color: #1a7a45; }
.log-reject  { color: #b52020; }
.log-chosen  { color: #6b21a8; font-weight: 700; }
.log-reset   { color: #888; }

// Code not found

Notice the key invariant: the acceptor always promises to ignore lower-numbered proposals, and always echoes back the highest-numbered proposal it already accepted. That tiny rule is what forces any two majorities to share at least one acceptor — and one shared acceptor is enough to carry the winning value forward.

Paxos is correct — but "correct" has a precise meaning here, and understanding it reveals a deep impossibility at the heart of distributed computing.

What Paxos guarantees:

• Safety: at most one value is ever chosen, even if messages are delayed, reordered, or duplicated, and even if any minority of nodes crashes.
• Liveness (with caveats): if a majority of nodes are up and can communicate, a value will eventually be chosen.

The FLP impossibility (Fischer, Lynch, Paterson, 1985): In a fully asynchronous network — where you cannot tell a crashed node from a very slow one — no deterministic consensus algorithm can guarantee both safety and termination. This is a proven impossibility result, as fundamental to distributed computing as the Halting Problem is to computation.

Paxos escapes FLP by not guaranteeing termination in adversarial message schedules. Two proposers can keep outbidding each other forever (dueling proposers), making no progress. Real deployments add a randomized back-off or elect a single distinguished leader to prevent this.

Other limits:

• Paxos needs a majority (quorum) of nodes to be live; it cannot tolerate n/2 or more failures out of n nodes.
• The CAP theorem (Brewer, 2000; proved by Gilbert & Lynch, 2002) says a distributed system cannot simultaneously guarantee Consistency, Availability, and Partition tolerance. Paxos chooses C and P over A: under a partition it stops rather than risk divergence.

Designing a consensus protocol is therefore a careful navigation of proven impossibility: Paxos gives you the strongest safety guarantee that is achievable, at the cost of availability when things go wrong. See also the halting problem and P vs NP for other famous impossibility and hardness results.

Paxos (and its descendants) is the invisible glue holding together every strongly consistent distributed system you rely on:

• Google Chubby / Spanner: Chubby (2006) was Google's first large-scale Paxos deployment, used for distributed lock management and metadata. Spanner uses Paxos per shard to achieve globally consistent timestamps.
• Apache ZooKeeper: uses Zab, a protocol in the same family, to replicate a coordination tree that thousands of distributed applications use for leader election and configuration.
• etcd: the consensus store behind Kubernetes uses Raft — a deliberately simpler re-explanation of Paxos — to keep cluster state consistent across control-plane nodes.
• Database replication: CockroachDB, TiDB, and YugabyteDB all use Raft (derived from Paxos) to replicate data across availability zones.
• Blockchain: Bitcoin's Nakamoto consensus is a probabilistic cousin solving the harder Byzantine fault model; Tendermint and PBFT are BFT protocols inspired by Paxos.
• Replicated state machines: any system that must replay a log of commands identically on multiple nodes — from distributed filesystems to payment processors — reduces to the consensus problem that Paxos solves.

The pattern recurs because the underlying need is universal: many machines, one truth.

Paxos answers one of the oldest questions in distributed computing: can machines that crash and restart ever reliably agree? The answer is yes — but the proof is subtle, the limitations are real, and the FLP impossibility theorem shows there is a hard ceiling on what any protocol can promise.

Every time you push a commit, deploy a container, or make a payment that must not be lost, some variant of Paxos is almost certainly running underneath, quietly running its two-phase dance so that a cluster of fallible machines speaks with one voice.

The next time a server in a data center silently reboots mid-transaction, remember: Paxos was already there, holding the answer safe until the node came back to ask for it.