Paxos — History and the Problem — Consensus 5.1

Everything in Phases 1 through 4 has been building toward this moment: the algorithm that finally, correctly solves consensus under the full realistic failure model this series has insisted on since article 1.1 — crash failures and network partitions, together, with no unsafe trade-off like 3PC's (article 4.5). Leslie Lamport's Paxos, first written up in 1989 and published as "The Part-Time Parliament" in 1998, has one of the most unusual publication histories in computer science — a genuinely brilliant algorithm nearly buried by its own paper's presentation. This article covers that history (it matters — it explains why Paxos has a reputation for being "hard" that the algorithm itself doesn't fully deserve), and states the precise problem Paxos solves, setting up the mechanical walkthrough in article 5.2.

The strange history of "The Part-Time Parliament"

Lamport developed the algorithm in 1989, motivated by exactly the same gap this series has spent four phases building toward — the well-documented failure modes of 2PC and 3PC (articles 4.4, 4.5) under realistic, partition-prone networks. Rather than presenting it as a straightforward distributed-systems paper, Lamport wrote it as an elaborate allegory: a fictional Greek island called Paxos, whose part-time legislators (busy with their day jobs, not paying full attention) needed to pass laws by consensus despite constantly wandering in and out of the parliamentary chamber — a whimsical framing device for exactly the crash/asynchrony/partition failure model this article is about to state formally.

The allegory backfired, badly, and the delay is a genuinely instructive story about communicating technical ideas. Reviewers and readers found the ancient-Greek narrative device confusing and off-putting rather than illuminating — Lamport himself has written that the paper was initially rejected, and even after eventual publication in 1998 (a full nine years after he wrote it), it took years more before the wider distributed-systems community fully absorbed and trusted the algorithm. Lamport later wrote a much more direct, allegory-free explanation, "Paxos Made Simple" (2001), specifically to fix this communication failure — and that paper, not the original, is what most engineers actually learn Paxos from today. The lesson generalizes well beyond this one paper: a genuinely correct, important idea can sit unused for a decade if its presentation actively works against understanding it — worth remembering as this series works through several more papers with their own communication quirks in Phase 10.

Why the delay mattered for the field, not just Lamport

This isn't just an amusing anecdote — the delay had real, traceable consequences for the field this series has been tracing. Google's Chubby lock service paper (2006) and the Paxos-based systems that followed it are often credited with finally demonstrating Paxos's practical viability to a broad engineering audience — nearly two decades after Lamport first solved the problem. Several other algorithms this series will cover (Viewstamped Replication, article 5.4, developed independently around the same time as Paxos by Oki and Liskov, solving an overlapping problem with different terminology) suffered a similar fate of being under-recognized relative to their actual importance, partly for similar communication and timing reasons. Raft's 2014 paper (article 5.5 onward) is explicitly, by its authors' own stated design goal, a reaction to this entire history — "In Search of an Understandable Consensus Algorithm" is not a subtle title; Ongaro and Ousterhout built Raft specifically to solve the same problem as Paxos while avoiding Paxos's decades-long reputation for being needlessly difficult to teach and implement correctly.

The precise problem statement

With the full vocabulary from Phases 1-4 now available, the problem Paxos solves can be stated with complete precision — worth doing carefully, because this exact statement is what article 5.2's mechanical walkthrough proves the algorithm satisfies:

The single-decree consensus problem, precisely: a set of processes, any number of which may crash or become arbitrarily slow (article 1.1's failure spectrum, crash/omission/timing — but not Byzantine), communicating over an asynchronous network where messages may be arbitrarily delayed or lost but not corrupted or forged (article 1.1's "Lie #1," formalized) — must agree on a single value, satisfying: (Safety) only a value that was actually proposed can be chosen, and once any process learns that a value has been chosen, it never learns a different value was chosen (article 4.1's safety, unconditional); (Liveness) some proposed value is eventually chosen, and processes eventually learn it, given sufficient favorable conditions — a majority of processes up and communicating with each other for long enough (article 4.1's conditional liveness, article 2.5's partial-synchrony escape hatch).

Notice precisely how this statement threads every needle the previous four phases identified: it doesn't promise liveness unconditionally (FLP, article 2.5, proved that's impossible for a deterministic algorithm in full asynchrony) — but it promises safety unconditionally, in every execution, no matter how adversarial the scheduling (exactly the safety/liveness asymmetry from article 4.1). And it explicitly requires only a majority for liveness, not unanimity (exactly the fix article 4.5 identified as missing from 3PC's recovery logic) — which is precisely why Paxos, unlike 3PC, remains safe under partitions: the majority-overlap guarantee (article 3.3) makes it structurally impossible for two disjoint groups to both proceed independently and reach conflicting decisions.

Fig 1 — Every gap identified across Phases 1-4 is a specific requirement Paxos's problem statement is built to close.

The three roles: proposers, acceptors, learners

Before the mechanical walkthrough in article 5.2, it's worth introducing the three logical roles Paxos defines — a genuinely useful conceptual separation, even though in most real deployments a single physical process plays more than one role simultaneously:

Proposers — processes that propose values to be chosen. In practice, this is usually whichever process wants to get a write accepted (often, though not strictly required, a stable elected leader, echoing article 4.2's election machinery).
Acceptors — the processes that actually vote on proposals and collectively determine, via majority (article 3.3), which value gets chosen. This is where the algorithm's safety guarantees live.
Learners — processes that need to find out what value was chosen, without necessarily participating in the voting itself (useful for replicas that need to apply the decided value to their state machine, per article 3.1, without being part of the acceptor quorum).

This three-role separation is a deliberate design choice that pays off in flexibility: the same core protocol supports configurations ranging from "every process plays all three roles" (the common simple case) to more elaborate deployments where, say, a small dedicated set of acceptors handles voting while a much larger set of learners consumes the results — a pattern that resurfaces when this series covers read scaling and witness-node-style configurations again in later phases.

FAQ

Is "Paxos Made Simple" actually simple?

Simpler than the original allegorical paper, certainly, and it's the paper most working engineers should read first — but "simple" is relative; it still requires careful, close reading to fully internalize the two-phase protocol and its safety argument. Article 5.2 of this series aims to be an even more gradual, worked-example-driven on-ramp than either of Lamport's own papers, building directly on the vocabulary already established in Phases 1-4.

Why does this article distinguish "single-decree" consensus specifically?

Because Paxos, as originally described, solves the problem of agreeing on exactly one value — this is deliberately the simplest possible version of the problem, and it's precisely the version proven equivalent to atomic broadcast in article 4.3 (recall: a sequence of single consensus decisions builds a replicated log). Article 5.3 (Multi-Paxos) covers the practical extension to repeatedly deciding a whole sequence of values efficiently — which is what any real production log-replication system actually needs.

Did anyone solve this problem before Lamport, even informally?

The broader distributed-transactions and commit-protocol research (2PC in the 1970s, 3PC in 1981 — articles 4.4, 4.5) directly preceded and motivated Paxos, but those protocols, as this series has shown in detail, don't actually solve the majority-based, partition-safe version of the problem — Paxos is generally credited as the first algorithm to get the full, correct answer, even though (as the VR discussion in article 5.4 will show) Oki and Liskov developed an independent, overlapping solution around the same time using different terminology and framing.

Is Paxos actually used directly in production, or mostly Raft/its variants now?

Both, extensively — Google's Chubby, Spanner, and several internal systems use Paxos or Multi-Paxos variants directly (covered in Phase 9); Raft (5.5-5.6) has become the more common choice for new systems built after 2014 specifically because of its understandability advantage, but Paxos-family algorithms (including the modern Paxos family in Phase 7) remain very much live, actively-developed production technology, not a historical curiosity.

Takeaways

Lamport developed Paxos in 1989, but its allegorical "Part-Time Parliament" presentation delayed publication to 1998 and delayed broad adoption for years beyond that — a genuine cautionary tale about presentation mattering as much as correctness for an idea's real-world impact.
"Paxos Made Simple" (2001) is the direct, allegory-free follow-up most engineers actually learn from, and Raft (5.5 onward) was explicitly designed as a further reaction to this same communication problem.
The precise problem statement threads every gap identified across Phases 1-4: unconditional safety (only a proposed value is chosen, never two different ones) plus majority-conditional liveness (a value is eventually chosen, given a majority up and communicating) — exactly matching article 4.1's safety/liveness asymmetry and article 3.3's majority-overlap mechanism.
Paxos defines three logical roles — proposers, acceptors, learners — a separation that enables flexible deployment configurations beyond the simple "everyone plays every role" case.
Article 5.2 next: the actual mechanical two-phase protocol (Prepare/Promise, Accept/Accepted) that satisfies this problem statement, walked through with a full worked example.

References & further reading

Lamport — The Part-Time Parliament (1998) — the original paper, allegory and all; historically important, not the recommended starting point for learning the algorithm.
Lamport — Paxos Made Simple (2001) — the direct, allegory-free explanation; the standard starting reference.
Burrows — The Chubby Lock Service for Loosely-Coupled Distributed Systems (2006) — widely credited with demonstrating Paxos's practical production viability.
cvam.sight — Consensus 4.5: Three-Phase Commit (3PC) — the exact gap this article's problem statement is built to close.

Paxos — history and the problem.