Original: Leslie Lamport, Paxos Made Simple, ACM SIGACT News 32(4), December 2001. Canonical PDF: lamport.azurewebsites.net/pubs/paxos-simple.pdf Predecessor: The Part-Time Parliament, ACM TOCS 16(2), 1998 (the “island of Paxos” allegory that nobody could read).

Why “made simple”

Lamport originally described his consensus algorithm in 1998 in The Part-Time Parliament, a paper framed as archaeological reconstruction of the parliamentary procedures of an ancient Greek island. It was a joke. It was also, by broad consensus (pun deliberate), unreadable — reviewers hated it, adoption was near zero for years, and even engineers who wanted to build on it complained they couldn’t.

The 2001 Paxos Made Simple is the same algorithm without the parable. Its opening sentence is famously dry:

“The Paxos algorithm, when presented in plain English, is very simple.”

The rest of the paper is Lamport quietly demonstrating that yes, in fact, it is — once you strip out the archaeological framing.

What Paxos actually does

Paxos solves the single-decree consensus problem: a set of processes, some of which may crash or send delayed messages over an asynchronous network, must all agree on exactly one value. It does this with two roles played by the participating processes — proposers and acceptors — plus learners who observe the outcome — running through two phases:

  1. Prepare / Promise. A proposer picks a monotonically increasing proposal number n, sends prepare(n) to a majority of acceptors, and asks them to promise not to accept anything numbered lower. Acceptors who promise also return the highest-numbered proposal they’ve already accepted (if any).
  2. Accept / Accepted. If the proposer collects promises from a majority, it sends accept(n, v) — where v is either its own value or the value from the highest-numbered previously-accepted proposal it saw. If a majority accepts, the value is chosen.

That’s it. Everything else is scaffolding: leader election is an optimization to reduce dueling proposers; Multi-Paxos runs a sequence of these decrees to replicate a log; state-machine replication (Schneider 1990) is what you build on top to get a fault-tolerant service.

Why it still matters in 2026

Almost every serious distributed system in production runs some descendant of Paxos:

  • Google Chubby (2006) — Paxos directly, for lock service and metadata.
  • Google Spanner (2012) — Paxos groups per data shard, plus TrueTime for external consistency.
  • Apache ZooKeeper — Zab, a Paxos variant tuned for primary-backup replication.
  • etcd / Consul / TiKV / CockroachDB — Raft, which Ongaro & Ousterhout explicitly designed as “Paxos made understandable” (their word). Raft is Paxos with the parts that confused people — leader election coupled to log replication, log matching invariants — pulled to the front.
  • Aurora DSQL (the AWS paper covered in this week’s digest) — the Journal replication tier and adjudicators are descendants of the same intellectual lineage.

Even the systems that don’t use Paxos define themselves against it. FLP impossibility (Fischer, Lynch, Paterson 1985) proved deterministic consensus impossible in a purely asynchronous network with even one crash failure. Paxos is the answer to “yes, but what if we relax that just enough to be practical?” — it’s live only when a majority is up and communicating, which is almost always true in the real world.

What’s still hard

Reading the paper today, three things stand out that the field has spent 25 years grappling with:

  1. Single-decree vs. multi-decree. Lamport spends most of the paper on single-decree; the multi-decree extension (Multi-Paxos) is described in a few paragraphs at the end. In practice, Multi-Paxos is where all the complexity — leader leases, log compaction, membership changes, catch-up protocols — lives. Raft’s contribution is largely that it makes those parts explicit.
  2. Membership changes. Paxos as originally described assumes a fixed acceptor set. Reconfiguring it (adding/removing nodes) safely is subtle enough that Lamport wrote a whole follow-up paper (Reconfiguring a State Machine, 2010) about it.
  3. Byzantine variants. Paxos assumes crash faults only. PBFT (Castro & Liskov 1999), HotStuff (2019), and the BFT consensus underpinning modern blockchains all extend the same core idea to adversarial failures — with substantially more messages per decision.

Read this if

You’ve written “we use Raft” in a design doc without being able to explain why Raft exists. Twenty pages. Read the 2001 version, skip the 1998 one unless you enjoy archaeology.

Bibliography

@article{Lamport2001_paxos,
  title   = {Paxos Made Simple},
  author  = {Lamport, Leslie},
  journal = {ACM SIGACT News},
  volume  = {32},
  number  = {4},
  pages   = {51--58},
  year    = {2001},
  url     = {https://lamport.azurewebsites.net/pubs/paxos-simple.pdf}
}