On Ink Shortages

20 Oct 2017

In the original presentation of the Paxos algorithm, Lamport used an extended metaphor involving the legislators of a bygone civilization [1]. These legislators would communicate by messenger and pass (non-contradictory) laws. One of the key assumptions of this protocol was that the legislators had special ledgers they carried around and could write on with indelible ink.

This is my (almost certainly misguided) attempt at an allegorical explanation of our recent work on diskless recovery in distributed systems [2].

Naxos

Having recently undertaken a long archaeological study of my own, I discovered that, shortly after its development, the parliamentary protocol used on Paxos spread throughout the region and was adopted by other parliaments (curiously, always with a few tweaks and always with a letter or two prepended to the name “Paxos”).

The protocol eventually spread to the the far-away (though similarly-named) island of Naxos. The Naxons, however, were not as wealthy as the Paxons and could not afford the vast quantities of expensive indelible ink the Paxon legislators used to record their decrees. (All other available inks had a tendency to fade over time and were thus unsuitable for parliamentary business.) However, Naxon legislators—out of necessity—had prodigious memories, and when they committed to a promise during the legislative process, they did not forget it.

At first, the Naxon legislators used the multi-decree Paxos protocol without issue. This protocol worked perfectly well for a number of years, until the first time a Naxon legislator was replaced. The Naxon parliament had no term limits, and incumbents almost always won (thanks to massive campaign contributions from the olive oil industry), but when a challenger finally won election for the first time, something happened that had never happened before—the parliament passed contradictory laws.

The Incident

As per parliamentary procedure, Naxon legislators used each other’s official titles to conduct all business (e.g., the gentleman from Σεαττλε). While the aforementioned election was ongoing, the MP from Μουνταιν Ϝιεω attempted to pass a law making Λεσλιε the cheese inspector for the coming year. Μουνταιν Ϝιεω’s representative was able to secure votes for this decree from a majority of legislators—including an MP who was about to be replaced, the MP from Βοστον.

However, this process of gathering votes took quite a bit of time and lasted well past the election. After he was elected, the new legislator from Βοστον proposed a decree making Βαρβαρα the cheese inspector for the coming year, which was also able to pass. As you can imagine, this led to some controversy.

The Naxon political scientists were not complete neophytes and knew about the potential for problems when new legislators were elected; they had designed a procedure specifically to handle this process. Because this procedure had to work in the case of the death of an MP, the Naxon protocol could not rely on the ability of a newly elected legislator to learn all previous decisions from the former legislator of their district. The political scientists, therefore, decided that newly elected legislators would, upon election, contact a majority of the parliament to learn about previously agreed-to decrees and adopted ballots.

The problem arose during the passing of the decree to make Λεσλιε cheese inspector. The decree’s sponsor rightly reckoned that the old MP from Βοστον might be soon replaced, and so sent the vote request to him via express courier. While waiting for replies from the other legislators, the election happened, and the representative from Βοστον was replaced. The new Βοστον MP was able to learn about all new decrees from a majority before any in that majority received the request to make Λεσλιε cheese inspector. The representative from Μουνταιν Ϝιεω was away at his villa and did not learn about the election results but did receive the remaining votes for his decree. At this point, he had received votes from a majority of districts to make Λεσλιε cheese inspector, but it was not true at that moment that a majority of legislators in the current parliament knew about this decree. Thus, the new MP from Βοστον was able to also make Βαρβαρα cheese inspector (using a majority that did not know about the previous decision).

The Solution

At first, the Naxon political scientists blamed the inconsistency on corruption; members of the political elite in Naxos had a habit of taking vacations in Byzantium—to the Naxons, a clear sign of moral bankruptcy. However, they eventually spotted the problem and came up with a solution.

The Naxon parliament needed a way to distinguish different representatives from the same district. They decided to refer to each legislator by their district name and the year in which the legislator was first elected (e.g., the gentleman from Σεαττλε, first elected in the year 453).^{1 2} Then, in all of their messages to each other, the legislators included their current belief about the composition of the parliament. (I assume that the Naxons had a shorthand way of expressing this, but that particular detail has been lost to history.)

This procedure ensured that the cheese inspector incident could never happen again. Any legislator attempting to pass a decree while an election was ongoing would learn about any new legislators elected thanks to the added information attached to each parliamentary message (or the decree would complete before the new legislator could become an active member of parliament). In the example above, the Μουνταιν Ϝιεω representative would have found out that the incumbent from Βοστον had been replaced. When this happened, under the new rules, the Μουνταιν Ϝιεω MP would have to contact the new representative from the district before considering that district’s vote as counting towards a majority.

There is archaeological evidence to suggest that the Naxons realized this process of assembling majorities and replacing legislators could be used for other civic procedures, ones with weaker requirements than their law-making process, but exactly what procedures they did invent, we cannot say for sure.

How Paxos Solved the Succession Problem

On Paxos, thanks to their permanent ledgers and indelible ink, the succession problem was solved much more simply. A new legislator would be given at the start of their term the ledger of their predecessor and would continue on with the protocol as normal.

References

1. Lamport, L. The Part-time Parliament. ACM Transactions on Computer Systems. 16(2):133–169. May 1998.
2. Michael, E., Ports, D.R.K., Sharma, N.K. and Szekeres, A. Recovering Shared Objects Without Stable Storage. In Proceedings of the 31st International Symposium on Distributed Computing (DISC ’17). Vienna, Austria. Oct. 2017.