Leslie Lamport Wrote Paxos as a Lost Greek Parliament. Referees Called It ‘Not Very Important.’

In 1990, Leslie Lamport submitted Paxos to the journal ACM Transactions on Computer Systems as the story of a parliament on an ancient Greek island. Paxos is his algorithm for keeping a group of computers in agreement when some of them crash.

All three referees, by his account, found the paper “mildly interesting, though not very important,” and said that “all the Paxos stuff” had to be removed.

Lamport was “quite annoyed at how humorless everyone working in the field seemed to be.” So he “did nothing with the paper.”

The journal printed it in May 1998, eight years after he submitted it.

The Greek setting was a deliberate choice. Lamport had already popularized the consensus problem, how unreliable computers can agree on anything, by describing it with Byzantine generals. Inspired by that success, he cast his new algorithm as a parliament on an island that Leo Guibas suggested calling Paxos. Writing about a lost civilization, he explained, let him “eliminate uninteresting details.” He even gave a few lectures as an Indiana-Jones-style archaeologist, “replete with Stetson hat and hip flask.”

By his own verdict, the humor was “a dismal failure.” “People who attended my lecture remembered Indiana Jones, but not the algorithm,” he wrote.

Among the people who received the paper “and who claimed to have read it,” Lamport wrote, were three experts in the field: Nancy Lynch, Vassos Hadzilacos and Phil Bernstein. A couple of months later he emailed them a question: “Can you implement a distributed database that can tolerate the failure of any number of its processes (possibly all of them) without losing consistency, and that will resume normal behavior when more than half the processes are again working properly?”

“None of them noticed any connection between this question and the Paxos algorithm.”

How Paxos keeps servers from choosing two different values

Without the legislators, Paxos solves the consensus problem: several servers, some of which may crash or answer late, must settle on a single value, such as which machine is in charge. In “Paxos Made Simple” (2001), Lamport laid out the mechanism in plain terms.

Every proposal carries a unique number. A value is chosen once a majority of the voting servers, which Lamport calls acceptors, have accepted a single proposal with that value.
A proposer first sends a prepare request with its number. Each acceptor that answers promises not to accept any lower-numbered proposal and reports the highest-numbered proposal it has already accepted, if any.
If any acceptor reports an accepted proposal, the proposer must reuse the value from the highest-numbered report instead of its own. A latecomer carries forward a value that may already have been chosen instead of overwriting it.

The key is the overlap: “any two majorities have at least one acceptor in common.” So once a value has been chosen, any majority that answers a later proposer includes at least one acceptor that accepted it. That is how Paxos stays consistent when a proposer crashes halfway through and another takes over.

Lamport’s colleagues who needed Paxos had no trouble with the parable

Lamport worked at Digital Equipment Corporation’s Systems Research Center, and some colleagues there read the same text without difficulty. Chandu Thekkath and Ed Lee were building a distributed system called Petal and needed a commit protocol so that operations would complete correctly when servers failed. They had found three-phase commit “a bit difficult to understand” and had given up on implementing it.

Lamport gave Lee a copy of the Paxos technical report. Thekkath later wrote that he “particularly liked its humour.” “Paxos had all the necessary properties we wanted for our system and we figured we could implement it,” he recalled. “A year later, when we needed a distributed lock server for the Frangipani file system we used Paxos again.”

Butler Lampson, Lamport wrote, “immediately understood the algorithm’s significance” and got Nancy Lynch, one of the three who had missed the connection, interested in Paxos.

Once Lynch, Lampson and Roberto De Prisco had published their own specification and proof, Lamport proposed the paper to Ken Birman, then the journal’s editor, who suggested a revision. Lamport judged the paper’s description and proof of the algorithm “precise and rigorous enough” and offered a shortcut instead: publish it as “a recently rediscovered manuscript, with annotations by Keith Marzullo.” That carried on the joke and, as Lamport put it, saved him work.

Some retellings shrink the 1990 episode into a plain rejection. A 2017 Brandeis Magazine profile said the journal “rejected it as insignificant” and later “reconsidered its decision.” In Lamport’s account, the referees wanted the Greek story removed, he chose not to revise, and he brought the paper back himself.

Simple to Lamport, hard for many engineers

At a conference in 2001, Lamport “got tired of everyone saying how difficult it was to understand the Paxos algorithm.” People, in his view, “got so hung up in the pseudo-Greek names” that they found the paper hard. The whole abstract of “Paxos Made Simple,” the paper he wrote in response, is one sentence: “The Paxos algorithm, when presented in plain English, is very simple.”

Others found it hard even without the Greek names. Google’s Chubby lock service, described in 2006, used the “not very important” algorithm to reach consensus among its replicas. In “Paxos Made Live” (2007), three Google engineers noted that Paxos can be described with a page of pseudo-code, while their complete implementation ran to several thousand lines of C++. In 2014, Diego Ongaro and John Ousterhout presented Raft, an alternative designed for understandability, because “Paxos is quite difficult to understand.” In their study, 33 of 43 students did better on questions about Raft than on questions about Paxos.

A test for your design documents, and where plain English stops

The most useful part of the story is Lamport’s email. It restated the problem in plain terms, with no island and no legislators. Three people who said they had read the paper did not connect the question to it.

That is a test any engineer can borrow. Before you rely on a design document, ask someone who has read it a question the document answers, phrased in words the document never uses. If they cannot connect the two, suspect the packaging, however clever, before you blame the reader.

Plain English has a limit, too. In 2015, Michael Deardeuff of Amazon told Lamport that one sentence in “Paxos Made Simple” is ambiguous. Read the wrong way, it leads to an incorrect algorithm, and Deardeuff had found that algorithm in a number of Paxos implementations on GitHub. Lamport will not remove the ambiguity or say where it is. His notes warn implementers away from the prose and toward a precise description instead: “Prose is not the way to precisely describe algorithms.”

Explore

Stay connected