The Part-Time Parliament

1 The Part-Time Parliament Leslie Lamport This article appeared in ACM Transactions on Computer Sys- tems 16, 2 (May 1998), 133-169. Minor corrections were made on 29 August 2000. The Part-Time Parliament LESLIE LAMPORT. Digital Equipment Corporation Recent archaeological discoveries on the island of paxos reveal that the Parliament functioned de- spite 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 forget- fulness of their messengers. The Paxon Parliament 's protocol provides a new way of implementing the state-machine approach to the design of distributed systems. Categories and Subject Descriptors: [Computer-Communications Networks]: Distributed Systems Network operating systems; [Operating Systems]: Reliability Fault-tolerance.

2 [Administrative Data Processing]: Government General Terms: Design, Reliability Additional Key Words and Phrases: State machines, three-phase commit, voting This submission was recently discovered behind a ling cabinet in the TOCS editorial o ce. Despite its age, the editor-in-chief felt that it was worth publishing. Because the author is currently doing eld 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 sci- ence. This is unfortunate; even though the obscure ancient Paxon civilization he describes is 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.

3 Indeed, some of the re nements the Paxons made to their protocol appear to be unknown in the systems literature. The author does give a brief discussion of the Paxon Parliament 's relevance to dis- tributed computing in Section 4. Computer scientists will probably want to read that section rst. Even before that, they might want to read the explanation of the algorithm for computer scientists by Lampson [1996]. The algorithm is also described more formally by De Prisco et al. [1997]. I have added further comments on the relation between the ancient protocols and more recent work at the end of Section 4. Keith Marzullo University of California, San Diego Authors' address: Systems Research Center, Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301.

4 Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or speci c permission. c 1998 ACM 0000-0000/98/0000-0000 $ 2 Leslie Lamport 1 The Problem The Island of paxos Early in this millennium, the Aegean island of paxos was a thriving mercantile cen- 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 willing to devote his life to Parliament .

5 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 corre- spondence 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.

6 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. Requirements Parliament 's primary task was to determine the law of the land, which was de ned by the sequence of decrees it passed. A modern Parliament will employ a secretary to record its actions, but no one in paxos was willing to remain in the Chamber throughout the session to act as secretary. Instead, each Paxon legislator main- tained a ledger in which he recorded the numbered sequence of decrees that were passed. For example, legislator 's ledger had the entry 155: The olive tax is 3 drachmas per ton if she believed that the 155th decree passed by Parliament set the tax on olives to 3.

7 Drachmas per ton. Ledgers were written with indelible ink, and their entries could not be changed. The rst requirement of the parliamentary protocol was the consistency of ledgers, meaning that no two ledgers could contain contradictory information. If legislator had the entry 132: Lamps must use only olive oil in his ledger, then no other legislator's ledger could have a di erent entry for decree 132. However, another legislator might have no entry in his ledger for decree 132 if he hadn't yet learned that the decree had been passed. Consistency of ledgers was not su cient, since it could be trivially ful lled by leaving all ledgers blank. Some requirement was needed to guarantee that decrees 1 It should not be confused with the Ionian island of Paxoi, whose name is sometimes corrupted to paxos .

8 The Part-Time Parliament 3. were eventually passed and recorded in ledgers. 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. Paxon legislators were willing to pass any decree that was proposed. However, their peripatetic propensity posed a problem. Consistency would be lost if one group of legislators passed the decree 37: Painting on temple walls is forbidden and then left for a banquet, whereupon a di erent group of legislators entered the Chamber and, knowing nothing about what had just happened, passed the con icting decree 37: Freedom of artistic expression is guaranteed Progress could not be guaranteed unless enough legislators stayed in the Cham- ber for a long enough time.

9 Because Paxon legislators were unwilling to curtail their outside activities, it was impossible to ensure that any decree would ever be passed. However, legislators were willing to guarantee that, while in the Chamber, they and their aides would act promptly on all parliamentary matters. This guar- antee allowed the Paxons to devise a parliamentary protocol satisfying the following progress condition. If a majority of the legislators2 were in the Chamber and no one entered or left the Chamber for a su ciently long period of time then any decree proposed by a legislator in the Chamber would be passed, and every decree that had been passed would appear in the ledger of every legislator in the Chamber. Assumptions The requirements of the parliamentary protocol could be achieved only by providing the legislators with the necessary resources.

10 Each legislator received a sturdy ledger in which to record the decrees, a pen, and a supply of indelible ink. Legislators might forget what they had been doing if they left the Chamber,3 so they would write notes in the back of the ledgers to remind themselves of important parliamentary tasks. An entry in the list of decrees was never changed, but notes could be crossed out. Achieving the progress condition required that legislators be able to measure the passage of time, so they were given simple hourglass timers. Legislators carried their ledgers at all times, and could always read the list of decrees and any note that had not been crossed out. The ledgers were made of the nest parchment and were used for only the most important notes.