The Part Time Parliament Morse-Books Pdf

The Part Time Parliament Morse
01 Jun 2020 | 29 views | 0 downloads | 33 Pages | 674.48 KB

Share Pdf : The Part Time Parliament Morse

Download and Preview : The Part Time Parliament Morse


Report CopyRight/DMCA Form For : The Part Time Parliament Morse



Transcription

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 C2 4 Computer Communications Networks Distributed. Systems Network operating systems D4 5 Operating Systems Reliability Fault tolerance. J 1 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 filing 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 field 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. Indeed some of the refinements 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 first 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, 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. specific permission,c 1998 ACM 0000 0000 98 0000 0000 00 00. 2 Leslie Lamport,1 The Problem,1 1 The Island of Paxos. Early in this millennium the Aegean island of Paxos was a thriving mercantile cen. ter 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 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 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 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. 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. 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 fulfilled 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. 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. 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. conflicting 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 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,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 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. finest parchment and were used for only the most important notes A legislator. would write other notes on a slip of paper which he might or might not lose if. he left the Chamber, The acoustics of the Chamber were poor making oratory impossible Legislators. could communicate only by messenger and were provided with funds to hire as. 2 In translating the progress condition I have rendered the Paxon word as majority. of the legislators Alternative translations of this word have been proposed and are discussed in. Section 2 2, 3 In one tragic incident legislator T developed irreversible amnesia after being hit on the.
head by a falling statue just outside the Chamber,4 Leslie Lamport. many messengers as they needed A messenger could be counted on not to garble. messages but he might forget that he had already delivered a message and deliver. it again Like the legislators they served messengers devoted only part of their. time to parliamentary duties A messenger might leave the Chamber to conduct. some business perhaps taking a six month voyage before delivering a message. He might even leave forever in which case the message would never be delivered. Although legislators and messengers could enter and leave at any time when. inside the Chamber they devoted themselves to the business of Parliament While. they remained in the Chamber messengers delivered messages in a timely fashion. and legislators reacted promptly to any messages they received. The o cial records of Paxos claim that legislators and messengers were scrupu. lously honest and strictly obeyed parliamentary protocol Most scholars discount. this as propaganda intended to portray Paxos as morally superior to its eastern. neighbors Dishonesty although rare undoubtedly did occur However because it. was never mentioned in o cial documents we have little knowledge of how Par. liament coped with dishonest legislators or messengers What evidence has been. uncovered is discussed in Section 3 3 5,2 The Single Decree Synod. The Paxon Parliament evolved from an earlier ceremonial Synod of priests that. was convened every 19 years to choose a single symbolic decree For centuries the. Synod had chosen the decree by a conventional procedure that required all priests. to be present But as commerce flourished priests began wandering in and out of. the Chamber while the Synod was in progress Finally the old protocol failed and. a Synod ended with no decree chosen To prevent a repetition of this theological. disaster Paxon religious leaders asked mathematicians to formulate a protocol for. choosing the Synod s decree The protocol s requirements and assumptions were es. sentially the same as those of the later Parliament except that instead of containing. a sequence of decrees a ledger would have at most one decree The resulting Synod. protocol is described here the Parliamentary protocol is described in Section 3. Mathematicians derived the Synod protocol in a series of steps First they proved. results showing that a protocol satisfying certain constraints would guarantee con. sistency and allow progress A preliminary protocol was then derived directly from. these constraints A restricted version of the preliminary protocol provided the. basic protocol that guaranteed consistency but not progress The complete Synod. protocol satisfying the consistency and progress requirements was obtained by. restricting the basic protocol 4, The mathematical results are described in Section 2 1 and the protocols are. described informally in Sections 2 2 2 4 A more formal description and correctness. proof of the basic protocol appears in the appendix. 4 The complete history of the Synod protocol s discovery is not known Like modern computer. scientists Paxon mathematicians would describe elegant logical derivations that bore no resem. blance to how the algorithms were actually derived However it is known that the mathematical. results Theorems 1 and 2 of Section 2 1 really did precede the protocol They were discovered. when mathematicians in response to the request for a protocol were attempting to prove that a. satisfactory protocol was impossible,The Part Time Parliament 5. 2 1 Mathematical Results, The Synod s decree was chosen through a series of numbered ballots where a ballot.
was a referendum on a single decree In each ballot a priest had the choice only. of voting for the decree or not voting 5 Associated with a ballot was a set of. priests called a quorum A ballot succeeded i if and only if every priest in the. quorum voted for the decree Formally a ballot B consisted of the following four. components Unless otherwise qualified set is taken to mean finite set 6. Bdec A decree the one being voted on, Bqrm A nonempty set of priests the ballot s quorum. Bvot A set of priests the ones who cast votes for the decree 7. Bbal A ballot number, A ballot B was said to be successful i Bqrm Bvot so a successful ballot was one. in which every quorum member voted, Ballot numbers were chosen from an unbounded ordered set of numbers If. Bbal Bbal then ballot B was said to be later than ballot B However this. indicated nothing about the order in which ballots were conducted a later ballot. could actually have taken place before an earlier one. Paxon mathematicians defined three conditions on a set B of ballots and then. showed that consistency was guaranteed and progress was possible if the set of. ballots that had taken place satisfied those conditions The first two conditions. were simple they can be stated informally as follows. B1 B Each ballot in B has a unique ballot number

Related Books

PETERSON S MASTER AP CALCULUS AB amp BC

PETERSON S MASTER AP CALCULUS AB amp BC

PETERSON S MASTER AP CALCULUS AB amp BC 2nd Edition W Michael Kelley Mark Wilding Contributing Author

AP Calculus AB amp BC Crash Course Advanced Placement AP

AP Calculus AB amp BC Crash Course Advanced Placement AP

Unlike other test preps our AP Calculus AB amp BC Crash Course gives you a review specifically focused on what you really need to study in order to ace the exam The review chapters offer you a concise way to learn all the important facts terms and concepts before the exam Topics that are exclusive to the BC version of the test are highlighted The introduction discusses the keys for success

Foundations amp Pre Calculus 10 Final Exam Review Package

Foundations amp Pre Calculus 10 Final Exam Review Package

Foundations amp Pre Calculus 10 Final Exam Review Package Adapted from Previous Ministry BC Provincial Exams Preparing people to thrive in meaningful lives Collingwood 2013 14 Black Carlbeck Hill Rickard Vidic Wong

AP Calculus BC Practice Exam

AP Calculus BC Practice Exam

AP Calculus BC Practice Exam CALCULUS BC SECTION I Part A Time 55 minutes Number of questions 27 A CALCULATOR MAY NOT BE USED ON THIS PART OF THE EXAMINATION Directions Solve each of the following problems After examining the choices select the choice that best answers the question No credit will be given for anything written in the test book In this test Unless otherwise specified

AP Calculus BC AP Exam Problems Chapters 1 3 Precalculus

AP Calculus BC AP Exam Problems Chapters 1 3 Precalculus

AP Calculus BC AP Exam Problems Chapters 1 3 1 Precalculus Review 1 If f is a continuous function defined for all real numbers x and if the maximum value of f x is 5 and the minimum value of f x is 7 then which of the following must be true I

BC CALCULUS REVIEW Uplift Education

BC CALCULUS REVIEW Uplift Education

BC CALCULUS REVIEW Intermediate Value Theorem for Continuous Functions If f x is continuous on a b and k is any number between f a and f b then there is at least one number c between a and b such that f c k The Intermediate Value Theorem IVT is only an existence theorem It does not explicitly

AP Calculus BC HILLGROVE

AP Calculus BC HILLGROVE

AP Calculus BC Exam Review 2 AP Calculus Review Here s what to expect for the next 5 weeks 1 Every assignment is graded and NO LATE PAPERS WILL BE ACCEPTED If you are going to miss class please have someone bring your paper to me when it is due 2 All graded assignments are determined on an AP scale as follows Percent AP Grade Class Grade out of 100 84 100 5 100 68 83 4 90 45

2006 Motorcycle Cross Reference catalog kdllink com

2006 Motorcycle Cross Reference catalog kdllink com

TRIUMPH Bonneville T100 2001 AA11111 AA55555 Y61 America Speedmaster amp Thruxton steering lock most models 1997 8001 9554 X270 TMC1 Pre 1990 s FS876 FS955 62FS S71B Ignition EJR1 EJR50 R62DM Steering VICTORY 1999 B111111 B444444 X259 Direct read tip to bow same system as 79 Kawasaki YAMAHA

Tuning Notes for the Triumph Bonneville Family of

Tuning Notes for the Triumph Bonneville Family of

Tuning Notes for the Triumph Bonneville Family of Motorcycles Includes the Bonneville T100 Thruxton Scrambler America and Speedmaster 2001 onwards Version 4 October 2005 Cat No CTN 01 Page 2 To order Phone 44 0 1722 711 745 About Tuning Why Tune At Jenks Bolts we get regular enquiries about tuning the Bonneville motor and the best carbu rettor setup for a

900 OHB FR Triumph Motorcycles

900 OHB FR Triumph Motorcycles

Ce manuel contient des informations sur les motos Triumph Bonneville Bonneville SE Bonneville T100 y compris la Steve McQueen Edition Bonneville 110 me Edition Thruxton et Scrambler Rangez toujours ce manuel du conducteur avec la moto Avertissement Attention et Note Tout au long de ce manuel du propri taire les informations particuli rement importantes sont pr sent es sous la

Microsoft Word Visual Basic for Applications

Microsoft Word Visual Basic for Applications

A a j