Introduction

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.

Try It: Paxos Rounds

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">3 proposers compete; 5 acceptors vote. Step through <b>Phase 1 (Prepare)</b> and <b>Phase 2 (Accept)</b> to watch Paxos converge on one agreed value.</div>
<div id="grid"></div>
<div class="controls">
  <button id="btn-prepare" type="button">Phase 1: Prepare</button>
  <button id="btn-accept"  type="button" disabled>Phase 2: Accept</button>
  <button id="btn-reset"   type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Single-decree Paxos simulation
// 3 Proposers, 5 Acceptors. A majority quorum = 3 acceptors.
// Each proposer has a proposal number n and a value v.
// Phase 1 (Prepare): proposer sends Prepare(n) to all acceptors.
//   Acceptor promises if n > its highest promised n; returns (promisedN, acceptedV).
// Phase 2 (Accept): if proposer gets >= 3 promises, it sends Accept(n, v*) where
//   v* = value from highest acceptedN among promises (or own value if none accepted yet). Acceptor accepts if n >= its promised n.
// The chosen value is the one accepted by a majority.

const NUM_PROPOSERS = 3;
const NUM_ACCEPTORS = 5;
const QUORUM = 3;
const PROPOSER_VALUES = ['Alpha', 'Beta', 'Gamma'];
// Spread proposal numbers so they don't collide
let proposalNs, proposers, acceptors;

function init() {
  // Give each proposer a distinct random proposal number (1-9 range, spaced)
  proposalNs = [
    Math.ceil(Math.random() * 3),
    Math.ceil(Math.random() * 3) + 3,
    Math.ceil(Math.random() * 3) + 6
  ];
  // Shuffle so it's not always proposer 3 that wins
  proposalNs.sort(() => Math.random() - 0.5);

  proposers = PROPOSER_VALUES.map((v, i) => ({
    id: i, value: v, n: proposalNs[i],
    promises: [],     // {acceptorId, promisedN, acceptedN, acceptedV}
    phase: 'idle',    // idle | prepare-sent | accept-sent | chosen | lost
    chosenValue: null
  }));

  acceptors = Array.from({length: NUM_ACCEPTORS}, (_, i) => ({
    id: i,
    promisedN: 0,
    acceptedN: 0,
    acceptedV: null
  }));
}

function runPhase1() {
  // Each proposer sends Prepare(n) to all acceptors
  // Acceptor responds with promise if n > promisedN
  const msgs = [];
  proposers.forEach(p => {
    p.phase = 'prepare-sent';
    let promiseCount = 0;
    p.promises = [];
    acceptors.forEach(a => {
      if (p.n > a.promisedN) {
        // Promise: update acceptor's promisedN
        const old = a.promisedN;
        a.promisedN = p.n;
        p.promises.push({ acceptorId: a.id, promisedN: p.n,
                          acceptedN: a.acceptedN, acceptedV: a.acceptedV });
        promiseCount++;
        msgs.push({ type: 'promise', proposer: p.id, acceptor: a.id, n: p.n, acceptedN: a.acceptedN, acceptedV: a.acceptedV });
      } else {
        msgs.push({ type: 'nack', proposer: p.id, acceptor: a.id, n: p.n, higherN: a.promisedN });
      }
    });
  });
  return msgs;
}

function runPhase2() {
  // Each proposer with >= QUORUM promises sends Accept(n, v*)
  const msgs = [];
  proposers.forEach(p => {
    if (p.promises.length < QUORUM) {
      p.phase = 'lost';
      msgs.push({ type: 'no-quorum', proposer: p.id, promises: p.promises.length });
      return;
    }
    // Determine value: use acceptedV from highest acceptedN among promises, or own value
    let highestAcceptedN = 0, chooseV = p.value;
    p.promises.forEach(pr => {
      if (pr.acceptedN > highestAcceptedN && pr.acceptedV !== null) {
        highestAcceptedN = pr.acceptedN; chooseV = pr.acceptedV;
      }
    });
    p.phase = 'accept-sent';
    let acceptCount = 0;
    acceptors.forEach(a => {
      if (p.n >= a.promisedN) {
        a.acceptedN = p.n; a.acceptedV = chooseV;
        acceptCount++;
        msgs.push({ type: 'accepted', proposer: p.id, acceptor: a.id, n: p.n, v: chooseV });
      } else {
        msgs.push({ type: 'rejected', proposer: p.id, acceptor: a.id, n: p.n, higherN: a.promisedN });
      }
    });
    if (acceptCount >= QUORUM) {
      p.phase = 'chosen'; p.chosenValue = chooseV;
      msgs.push({ type: 'chosen', proposer: p.id, v: chooseV, n: p.n });
    } else {
      p.phase = 'lost';
    }
  });
  return msgs;
}

// ── State for tracking cell highlights after each phase ──
// cellState[proposerIdx][acceptorIdx] = 'idle'|'promised'|'accepted'|'rejected'
let cellState;
let phase = 'init'; // init | after-phase1 | after-phase2

function resetCellState() {
  cellState = Array.from({length: NUM_PROPOSERS}, () =>
    Array.from({length: NUM_ACCEPTORS}, () => 'idle'));
}

function buildGrid() {
  const g = document.getElementById('grid');
  g.innerHTML = '';
  // Header row
  const corner = document.createElement('div');
  corner.className = 'gh row-h'; corner.textContent = ''; g.appendChild(corner);
  for (let a = 0; a < NUM_ACCEPTORS; a++) {
    const h = document.createElement('div');
    h.className = 'gh'; h.textContent = 'A' + (a + 1); g.appendChild(h);
  }
  // Data rows
  for (let p = 0; p < NUM_PROPOSERS; p++) {
    const rh = document.createElement('div');
    rh.className = 'gh row-h';
    rh.innerHTML = `P${p+1} <span style="font-weight:400;color:#668;margin-left:4px">n=${proposers[p].n} "${PROPOSER_VALUES[p]}"</span>`;
    g.appendChild(rh);
    for (let a = 0; a < NUM_ACCEPTORS; a++) {
      const c = document.createElement('div');
      const st = cellState[p][a];
      c.className = 'cell ' + st;
      c.id = 'cell-' + p + '-' + a;
      if (st === 'promised') {
        c.innerHTML = '<span class="label">promised</span><span class="val">✓</span>';
      } else if (st === 'accepted') {
        const v = acceptors[a].acceptedV || '';
        c.innerHTML = fmt('<span class="label">accepted</span><span class="val">%v%</span>', { v: v });
      } else if (st === 'rejected') {
        c.innerHTML = '<span class="label">rejected</span><span class="val">✗</span>';
      } else {
        c.innerHTML = '<span class="label">—</span>';
      }
      g.appendChild(c);
    }
  }
}

function appendLog(html, cls) {
  const d = document.getElementById('log');
  const line = document.createElement('div');
  line.className = cls || '';
  line.innerHTML = html;
  d.appendChild(line);
  d.scrollTop = d.scrollHeight;
}

function setup() {
  init(); resetCellState(); phase = 'init';
  buildGrid();
  document.getElementById('log').innerHTML = '';
  appendLog('Ready. Click <b>Phase 1: Prepare</b> to start.', 'log-reset');
  document.getElementById('btn-prepare').disabled = false;
  document.getElementById('btn-accept').disabled = true;
}

document.getElementById('btn-prepare').addEventListener('click', () => {
  const msgs = runPhase1();
  msgs.forEach(m => {
    if (m.type === 'promise') {
      cellState[m.proposer][m.acceptor] = 'promised';
      const acc = m.acceptedV ? " " + fmt('(prev: n=%acceptedN% v="%acceptedV%")', { acceptedN: m.acceptedN, acceptedV: m.acceptedV }) : '';
      appendLog(fmt('P%v%→A%v2%: <b>Promise</b> for n=%n%%acc%', { v: m.proposer+1, v2: m.acceptor+1, n: m.n, acc: acc }), 'log-prepare');
    } else {
      cellState[m.proposer][m.acceptor] = 'rejected';
      appendLog(fmt('P%v%→A%v2%: <b>Nack</b> (already promised n=%higherN%)', { v: m.proposer+1, v2: m.acceptor+1, higherN: m.higherN }), 'log-reject');
    }
  });
  phase = 'after-phase1';
  buildGrid();
  document.getElementById('btn-prepare').disabled = true;
  document.getElementById('btn-accept').disabled = false;
});

document.getElementById('btn-accept').addEventListener('click', () => {
  const msgs = runPhase2();
  msgs.forEach(m => {
    if (m.type === 'accepted') {
      cellState[m.proposer][m.acceptor] = 'accepted';
      appendLog(fmt('P%v%→A%v2%: <b>Accept</b> n=%n% v="%v3%"', { v: m.proposer+1, v2: m.acceptor+1, n: m.n, v3: m.v }), 'log-accept');
    } else if (m.type === 'rejected') {
      // already rejected in phase1; keep cell state
      appendLog(fmt('P%v%→A%v2%: <b>Rejected</b> accept (promised n=%higherN%)', { v: m.proposer+1, v2: m.acceptor+1, higherN: m.higherN }), 'log-reject');
    } else if (m.type === 'no-quorum') {
      appendLog(fmt('P%v%: only %promises% promise(s) — no quorum, giving up', { v: m.proposer+1, promises: m.promises }), 'log-reject');
    } else if (m.type === 'chosen') {
      appendLog(fmt('🎉 <b>CHOSEN</b>: P%v% achieved quorum with n=%n% → value = "<b>%v2%</b>"', { v: m.proposer+1, n: m.n, v2: m.v }), 'log-chosen');
    }
  });
  phase = 'after-phase2';
  buildGrid();
  document.getElementById('btn-accept').disabled = true;
});

document.getElementById('btn-reset').addEventListener('click', setup);
setup();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/paxos/Content licensed under CC BY-NC 4.0.