A mathematical algorithm, greek politics and a bunch of priests…this is what you need for the most beautiful paper I have ever read.
This week I am bringing you a paper about the Paxos distributed consensus algorithm. It got its name from an island in the aegean sea, or more accurate: From a way how the parliament of that island conducted legislation. The paper is long (33 pages), but beautifully written and explains the algorithm in a nice way. You got to check it out.
Here is the first paragraph:
1.1 The Island of Paxos
“The Part-Time Parliament” – Leslie Lamport
Early in this millennium, the Aegean island of Paxos was a thriving mercantile center. Wealth led to political sophistication, and the Paxons replaced their ancient theocracy with a parliamentary form of government. But trade came before civic duty, and no one in Paxos was willingto devote his life to Parliament. The Paxon Parliament had to function even though legislators continually wandered in and out
of the parliamentary Chamber. The problem of governing with a part-time parliament bears a remarkable correspondence to the problem faced by today’s fault-tolerant distributed systems, where legislators correspond to processes and leaving the Chamber corresponds to failing. The Paxons’ 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. Paxon civilization was destroyed by a foreign invasion, and archeologists have just recently begun to unearth its history. Our knowledge of the Paxon Parliament is therefore fragmentary. Although the basic protocols are known, we are ignorant of many details. Where such details are of interest, I will take the liberty of speculating on what the Paxons might have done
Abstract:
Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators. The legislators maintained consistent copies of the parliamentary record, despite their frequent forays from the chamber and the forgetfulness of their messengers. The Paxon parliament’s protocol provides a new way of implementing the state-machine approach to the design of distributed systems
Download Link:
http://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
Additional Links:
- None this time