The Part-Time ParliamentLESLIE LAMPORTDigital Equipment CorporationRecent archaeological discoveries on the island of Paxos reveal that the parliament functioneddespite the peripatetic propensity of its part-time legislators. The legislators maintainedconsistent copies of the parliamentary record, despite their frequent forays from the chamberand the forgetfulness of their messengers. The Paxon parliament’s protocol provides a newway of implementing the state machine approach to the design of distributed systems.Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distrib-uted Systems—network operating systems; D.4.5 [Operating Systems]: Reliability—fault-tolerance; J.1 [Computer Applications]: Administrative Data Processing—governmentGeneral Terms: Design, ReliabilityAdditional Key Words and Phrases: State machines, three-phase commit, voting1. THE PROBLEM1.1 The Island of PaxosEarly in this millennium, the Aegean island of Paxos was a thrivingmercantile center.1Wealth led to political sophistication, and the Paxonsreplaced their ancient theocracy with a parliamentary form of government.But trade came before civic duty, and no one in Paxos was willing to devotehis life to Parliament. The Paxon Parliament had to function even thoughlegislators continually wandered in and out of the parliamentary Chamber.The problem of governing with a part-time parliament bears a remark-able correspondence to the problem faced by today’s fault-tolerant distrib-uted systems, where legislators correspond to processes, and leaving theChamber corresponds to failing. The Paxons’ solution may therefore be ofsome interest to computer scientists. I present here a short history of thePaxos Parliament’s protocol, followed by an even shorter discussion of itsrelevance for distributed systems.Author’s address: Systems Research, Digital Equipment Corporation, 130 Lytton Avenue, PaloAlto, CA 94301.Permission to make digital/hard copy of part or all of this work for personal or classroom useis granted without fee provided that the copies are not made or distributed for profit orcommercial advantage, the copyright notice, the title of the publication, and its date appear,and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, torepublish, to post on servers, or to redistribute to lists, requires prior specific permissionand/or a fee.© 1998 ACM 0734-2071/98/0500–0133 $5.001It should not be confused with the Ionian island of Paxoi, whose name is sometimes corruptedto Paxos.ACM Transactions on Computer Systems, Vol. 16, No. 2, May 1998, Pages 133–169.Paxon civilization was destroyed by a foreign invasion, and archeologistshave just recently begun to unearth its history. Our knowledge of thePaxon Parliament is therefore fragmentary. Although the basic protocolsare known, we are ignorant of many details. Where such details are ofinterest, I will take the liberty of speculating on what the Paxons mighthave done.1.2 RequirementsParliament’s primary task was to determine the law of the land, which wasdefined by the sequence of decrees it passed. A modern parliament willemploy a secretary to record its actions, but no one in Paxos was willing toremain in the Chamber throughout the session to act as secretary. Instead,each Paxon legislator maintained a ledger in which he recorded thenumbered sequence of decrees that were passed. For example, Liˇnx’slegislator had the entry155: The olive tax is 3 drachmas per tonif she believed that the 155th decree passed by Parliament set the tax onolives to 3 drachmas per ton. Ledgers were written with indelible ink, andtheir entries could not be changed.The first requirement of the parliamentary protocol was the consistencyof ledgers, meaning that no two ledgers could contain contradictory infor-mation. If legislatorFis«rhad the entry132: Lamps must use only olive oil.134 • L. LamportACM Transactions on Computer Systems, Vol. 16, No. 2, May 1998.in his ledger, then no other legislator’s ledger could have a different entryfor decree 132. However, another legislator might have no entry in hisledger for decree 132 if he had not yet learned that the decree had beenpassed.Consistency of ledgers was not sufficient, since it could be triviallyfulfilled by leaving all ledgers blank. Some requirement was needed toguarantee that decrees were eventually passed and recorded in ledgers. Inmodern parliaments, the passing of decrees is hindered by disagreementamong legislators. This was not the case in Paxos, where an atmosphere ofmutual trust prevailed. Paxon legislators were willing to pass any decreethat was proposed. However, their peripatetic propensity posed a problem.Consistency would be lost if one group of legislators passed the decree37: Painting on temple walls is forbiddenand then left for a banquet, whereupon a different group of legislatorsentered the Chamber and, knowing nothing about what had just happened,passed the conflicting decree37: Freedom of artistic expression is guaranteedProgress could not be guaranteed unless enough legislators stayed in theChamber for a long enough time. Because Paxon legislators were unwillingto curtail their outside activities, it was impossible to ensure that anydecree would ever be passed. However, legislators were willing to guaran-tee that, while in the Chamber, they and their aides would act promptly onall parliamentary matters. This guarantee allowed the Paxons to devise aparliamentary protocol satisfying the following progress condition.If a majority of the legislators2were in the Chamber, and no one entered or leftthe Chamber for a sufficiently long period of time, then any decree proposed bya legislator in the Chamber would be passed, and every decree that had beenpassed would appear in the ledger of every legislator in the Chamber.1.3 AssumptionsThe requirements of the parliamentary protocol could be achieved only byproviding the legislators with the necessary resources. Each legislatorreceived a sturdy ledger in which to record the decrees, a pen, and a supplyof indelible ink. Legislators might forget what they had been doing if theyleft the Chamber,3so they would write notes in the back of the ledgers toremind themselves of important parliamentary tasks. An entry in the list ofdecrees was never changed, but notes could be crossed out. Achieving the2In translating the progress condition, I have rendered the Paxon wordmad§vritiˇs«tasmajority of