The Part Time Parliament LESLIE LAMPORT Digital Equipment Corporation 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 Categories and Subject Descriptors C 2 4 Computer Communication Networks Distributed Systems network operating systems D 4 5 Operating Systems Reliability faulttolerance J 1 Computer Applications Administrative Data Processing government General Terms Design Reliability Additional Key Words and Phrases State machines three phase commit voting 1 THE PROBLEM 1 1 The Island of Paxos Early in this millennium the Aegean island of Paxos was a thriving mercantile center 1 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 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 Author s address Systems Research Digital Equipment Corporation 130 Lytton Avenue Palo Alto CA 94301 Permission to make digital hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial 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 to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee 1998 ACM 0734 2071 98 0500 0133 5 00 1 It should not be confused with the Ionian island of Paxoi whose name is sometimes corrupted to Paxos ACM Transactions on Computer Systems Vol 16 No 2 May 1998 Pages 133 169 134 L Lamport 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 1 2 Requirements Parliament s primary task was to determine the law of the land which was defined 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 maintained a ledger in which he recorded the numbered sequence of decrees that were passed For example L i nx s legislator 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 drachmas per ton Ledgers were written with indelible ink and their entries could not be changed The first requirement of the parliamentary protocol was the consistency of ledgers meaning that no two ledgers could contain contradictory information If legislator F is r had the entry 132 Lamps must use only olive oil ACM Transactions on Computer Systems Vol 16 No 2 May 1998 The Part Time Parliament 135 in his ledger then no other legislator s ledger could have a different entry for decree 132 However another legislator might have no entry in his ledger for decree 132 if he had not yet learned that the decree had been passed Consistency of ledgers was not sufficient since it could be trivially fulfilled by leaving all ledgers blank Some requirement was needed to guarantee that decrees 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 different group of legislators entered the Chamber and knowing nothing about what had just happened passed the conflicting decree 37 Freedom of artistic expression is guaranteed Progress could not be guaranteed unless enough legislators stayed in the Chamber for a long enough time 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 guarantee 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 sufficiently 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 1 3 Assumptions The requirements of the parliamentary protocol could be achieved only by providing the legislators with the necessary resources 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 2 In translating the progress condition I have rendered the Paxon word mad vriti s t as majority of the legislators Alternative translations of this