PAPERS-15-003 · Paper — Paxos — The Part-Time Parliament

The paper

The paper “Paxos — The Part‑Time Parliament” introduced a landmark consensus algorithm that reshaped how distributed systems achieve agreement.

Before this paper

Before this work, reaching agreement in an asynchronous system where machines could crash and messages could be lost or delayed was known to be extremely subtle. Existing protocols were either wrong, unproven, or impractical. Researchers struggled with safety guarantees when some participants failed. The field needed a clear, provably correct solution.

The key idea

Lamport’s key insight was to use a simple majority‑quorum mechanism that lets a set of machines agree on a single value and never disagree, even if some crash and messages are delayed, as long as a majority stays alive. By requiring overlapping majorities, the algorithm ensures only one value can ever be chosen. This insight gave the first widely‑adopted, provably‑correct consensus protocol.

How it works

The protocol assigns three roles: proposers, acceptors, and learners. A proposer starts a two‑phase process. First, it sends a ‘prepare’ request with a unique proposal number to a majority of acceptors; each acceptor promises not to accept any older proposals and reports any value it has already accepted. Next, the proposer issues an ‘accept’ request with the chosen value; if a majority of acceptors accept it, the value is considered chosen. Learners then learn the chosen value from the acceptors. Because any two majorities overlap, safety is guaranteed.

See it — agreeing on one value

flowchart LR
  A["Proposer picks<br/>a number"] --> B["Prepare: ask a<br/>majority"]
  B --> C["Accept: majority<br/>agrees on value"]
  C --> D["Value chosen<br/>+ durable"]

What they showed

Paxos proved that safe consensus is achievable with a simple majority‑quorum mechanism, establishing a concrete result that a single value can be chosen reliably despite failures.

What it changed

The paper’s result underpins Google’s Chubby service and the consensus core of countless databases and coordination systems. Its practical success showed that rigorous theory could be deployed at scale. The difficulty of understanding Paxos later inspired the creation of the more approachable Raft algorithm. Next: ZooKeeper.

The one-line takeaway

A majority‑quorum is enough to achieve safe consensus even in the face of crashes and delays.

Read it / meet it

Reading the original paper gives insight into the elegant reasoning behind modern distributed systems. Today you encounter Paxos‑style consensus in many cloud services, databases, and lock managers that keep data consistent across the globe.