The Paxos protocol reached the research literature through “The Part-Time Parliament,” published in ACM Transactions on Computer Systems in 1998. Leslie Lamport presented the consensus algorithm as the story of a part-time parliament on the Greek island of Paxos, whose legislators pass decrees despite frequently leaving the chamber and losing messages. The conceit was meant to make the algorithm memorable, but many readers found that it obscured rather than clarified the underlying mechanism.
In response, Lamport wrote “Paxos Made Simple,” whose PDF metadata records a creation date of November 2001. It drops the allegory and states the algorithm plainly: how proposers and acceptors interact, why overlapping majorities make the agreed value stable, and how repeated instances of the protocol produce an ordered log through multi-Paxos.
Together the two papers form the primary record of Paxos. The first established the protocol and its correctness; the second made it teachable. Both are hosted on Lamport’s own publications site, where he also recounts the unusual history of the first paper’s long road to publication.
The pair has shaped how production systems achieve fault tolerance and remains a standard reference for distributed consensus, even as later work such as Raft set out to present the same guarantees in a more approachable way.