Perception

The Greek island of Paxos has way too many mysteries, for both archaeologists and computer scientists. When I was first reading Dr. Leslie Lamport’s The Part-time Parliament, which was an epic introduction of a novel consensus protocol designed for distributed systems, I genuinely wondered who that group of archaeologists were and how Dr. Lamport managed to discover such perfect analogies between an ancient democracy and distributed computer systems. To be honest I almost planned my visit to the archaeology department myself.

It wasn’t long before I sensed something wrong and looked things up on the web. The Greek island of Paxos does actually exist, but that’s about the only true thing outside of the context of Dr. Lamport’s article. The earlier senses of astonishment suddenly became streams of amusement after that point. Dr. Lamport was a more of a story teller than a mathematician or computer scientist, though he was attempting the “mission impossible” of educating people who weren’t as brilliant about his obscure algorithm. The fact that his article didn’t get published until 8 years after submission served as a fair evaluation of how well he did: it was fun to read, but things didn’t go too well obviously.

The research community actually considers The Part-time Parliament an example of a failed attempt to explain a protocol. I want to be a little easy on Dr. Lamport mostly out of two reasons. First, any consensus protocol is intrinsically difficult to explain, especially if one want to convince the audience of its correctness. This might be a false statement given the possibility that some unbelievably simple and correct protocols exist but are yet to be discovered, but based on what we have today it’s not unfair to say Paxos is the only one that convinced me of its correctness in its original form. Second, it is perhaps THE most entertaining research paper to read. How can I say no to such a brilliant presentation embedded with Athenian humor?

To be honest, the Paxos paper (a.k.a. The Part-time Parliament) is not a good example of using metaphors, but perhaps a very real bad example of over-using such metaphors. Despite that, I did like the approach Dr. Lamport chose to present his idea – it added entertainment values to this article so that readers like me followed through it all the way to the end at least for the sake of those classic quotes scattered around. Now let me share some with you so you can decide on your own whether or not to read the article. Bear in mind that they all came from a supposedly technical paper to be published on an academic journal.

“The Paxon’s solution may therefore be of some interest to computer scientists. I present here a short history of the Paxos Parliament’s protocol, followed by an even shorter discussion of its relevance for distributed systems.”

“In modern parliaments, the passing of decrees is hindered by disagreement among legislators. This was not the case in Paxos, where an atmosphere of mutual trust prevailed.”

“Legislators might forget what they had been doing if they left the Chamber…” Footnote: “In one tragic incident, legislator developed irreversible amnesia after being hit on the head by a falling statue just outside the Chamber.”

“A messenger might leave the Chamber to conduct some business – perhaps taking a six-month voyage – before delivering a message.”

“The Synod’s decree was chosen through a series of numbered ballots, where a ballot was a referendum on a single decree. In each ballot, a priest had the choice only of voting for the decree or not voting.” Footnote: “Like some modern nations, Paxos had not fully grasped the nature of Athenian democracy.”

“They were not as sophisticated as modern mathematicians, who can omit many details and write paragraph-style proofs without ever making a mistake.”

“To maintain B2, a ballot’s quorum was chosen to contain a of priests. Initially, just meant a simple majority. Later, it was observed that fat priests were less mobile and spent more time in the Chamber than thin ones, so a was taken to mean any set of priests whose total weight was more than half the total weight of all priests, rather than a simple majority of the priests. When a group of thin priests complained that this was unfair, actual weights were replaced with symbolic weights based on a priest’s attendance record.”

“The derivation of the basic protocol from B1-B3 made it obvious that the consistency condition was satisfied. However, some similarly ‘obvious’ ancient wisdom had turned out to be false, and skeptical citizens demanded a more rigorous proof.”

“Given the sophistication of Paxon mathematicians, it is widely believed that they must have found an optimal algorithm to satisfy the presidential election requirement. We can only hope that this algorithm will be discovered in future excavations on Paxos.”

“The president of parliament was originally chosen by the method that had been used in Synod, which was based purely on the alphabetical ordering of names. Thus, when legislator returned from a six-month vacation, he was immediately made president – even though he had no idea what had happened in his absence. Parliamentary activity came to a halt while , who was a slow writer, laboriously copied six months worth of decrees to bring his ledger up to date.

This incident led to a debate about the best way to choose a president. Some Paxons urged that once a legislator became president, he should remain president until he left the Chamber. An influential group of citizens wanted the richest legislator in the Chamber to be the president, since he could afford to hire more scribes and other servants to help him with the presidential duties. They argued that once a rich legislator had brought his ledger up to date, there was no reason for him not to assume the presidency. Others, however, argued that the most upstanding citizen should be made president, regardless of wealth. Upstanding probably meant less likely to be dishonest, although no Paxon would publicly admit the possibility of official malfeasance. Unfortunately, the outcome of this debate is not known; no record exists of the presidential selection protocol that was ultimately used.”

“It soon became evident that selecting bureaucrats was not as simple as it first seemed. Parliament passed a decree making the first cheese inspector. After some months, merchants complained that was too strict and was rejecting perfectly good cheese.”

(Try translating that into English letters to see who the first cheese inspector was)

“In fact, the mechanism for choosing legislators led to the downfall of the Parliamentary system in Paxos. Because of a scribe’s error, a decree that was supposed to honor sailors who had drowned in a shipwreck instead declared them to be the only members of Parliament. Its passage prevented any new decrees from being passed – including the decrees proposed to correct the mistake. Government in Paxos came to a halt. A general named took advantage of the confusion to stage a coup, establishing a military dictatorship that ended centuries of progressive government. Paxos grew weaker under a series of corrupt dictators, and was unable to repel an invasion from the east that led to the destruction of its civilization.”

(Again, see who that general was…)

From the editor:

“This submission was recently discovered behind a filing cabinet in the TOCS editorial office. Despite its age, the editor-in-chief felt that it was worth publishing. Because the author is currently doing field work in the Greek isles and cannot be reached, I was asked to prepare it for publication.

The author appears to be an archeologist with only a passing interest in computer science. This is unfortunate; even though the obscure ancient Paxon civilization he describes it of little interest to most computer scientists, its legislative system is an excellent model for how to implement a distributed computer system in an asynchronous environment. Indeed some of the refinements the Paxons made to their protocol appear to be unknown in the system literature.”

Dr. Lamport was recently awarded the 2013 ACM Turing Award, mostly for his contribution on the Paxos consensus algorithm.

The cited article can be accessed for free from here. Dr. Lamport holds the copyright of the original article.