The Part-Time Parliament Leslie LamportPresented byBhagya BethalaIsland of Paxosn The Aegean island, a thriving mercantilecentern Trade given more importance over civil dutiesn No one in Paxos willing to devote time toparliamentn Paxon parliament needed to function – todetermine law of the land (sequence ofdecrees) -- with legislators wandering in andoutWhy study Paxon parliament’sfunction?Problem of governing with a part-timeparliament Û consensus problem in fault-tolerant distributed systems, where legislatorscorrespond to processes, and leaving tofailingPaxon environment and assumptionsn Each legislator maintained a ledger in whichdecrees passed were recordedn Entries once made cannot be deleted ormodifiedn Legislators can leave any time and returnafter arbitrary amount of timen Legislators communicated only throughmessengersn A message can begarbled/lost/duplicated/delayedPaxon environment and assumptions(contd.)n Every legislator in the parliament cancommunicate to every other member presentn Time to deliver a message within theparliament is knownn Legislators react promptly while theyremained in the parliament to any receivedmessagesRequirementsn Consistency of the ledgers, i.e no two ledgerscould contain contradictory informationn Progress is needed to guarantee that somedecree will eventually be passed andrecordedn If a majority of the legislators were in the Chamber, and noone entered or left for sufficiently long period of time, thenany decree proposed by a legislator in the Chamber wouldbe passed, and every decree that had been passed wouldappear in the ledger of the every legislator in the ChamberDefinitionsn Ballot -- referendum on a single decreen Bdec – A decreen Bqrm– A non-empty set of priests, calledquorumn Bvot – A set of priests who cast voten Bbal – A ballot numberA ballot B is successful iff Bqrm C BvotSingle-decree Synodn Ledger would have at most one decreen A decree is chosen through a series ofballots.n Each priest has the choice of voting or notn The Paxon parliament protocol actuallyevolved from the Synod protocolConditions for consistency andprogressn For a set of ballots Tn B1(b) Each ballot in T has a unique ballotnumbern B2(b) The quorums of any two ballots in Thave at least one priest in commonn B3(b) for every ballot B in T, if any priest in B’squorum voted in an earlier ballot in T, then thedecree of B equals the decree of the latest ofthose earlier ballotsVotingMore definitionsn Vote v, contains three componentsn A priest Vpstn A ballot number Vbaln A decree Vdecn (Vpst, -∞, BLANK) --- null voten Votes(T) all votes v such that Vpst belongs toBvot, Vbal = Bbal and Vdec = Bdec for some B _ Tn MaxVote(b, p, B) is largest vote in{v _ Votes(B) : (Vpst = p)&(Vbal < b)}U{nullp}TheoremIf B1 – B3 hold for T, then((Bqrm C Bvot) & (B’qrm C B’vot)) => (B’dec = Bdec)for any B, B’ in TProof idea: By contradiction. LetY(B, T) = { B’ _ T: (B’bal > Bbal)&(B’dec != Bdec)}Show that Bqrm C Bvot then Y(B, T) is emptyC _ Y(B, T), such that Cbal = min{B’bal: B’ _ Y}MaxVote(Cbal, Cqrm, T)bal > BbalMaxVote(Cbal, Cqrm, T) _ Votes(Y(B, T))MaxVote(Cbal, Cqrm, T)bal < CbalSynod protocol(1) Priest p chooses a new ballot number b and sendsmessage NextBallot(b) to some set of priests(2) A priest q responds with LastVoted(b,v), the largestballot number less then b that he has voted for usingback of his ledger. If such a vote doesn’t exist, then adefault value nullq is used. v = MaxVote(b,q,T) (3) After p receives a LastVoted(b,v) message from allthe priests in a majority set Q, he initiates a newballot with number b, quorum Q, and decree d,chosen according to B3. He then records the newballot and sends BeginBallot(b,d) to QSynod protocol(4) Upon receipt of BeginBallot(b,d), if priestq decides to vote, then he sends Voted(b,q)to p and he records the vote in the back of hisledger(5) If p has recieved a Voted(b,q) from everypriest q in Q, then he writes d in his ledgerand sends Success(d) to all priests.(6) After receiving Success(d), a priest entersdecree d in his ledger.Priest’s jobn By sending LastVote(b,v), a priest ispromising not to cast vote for any ballot withnumber b’, where, Vbal < b’ < bn A priest recordsn the number of every ballot he has initiatedn every vote he has castn every LastVote message he has sentToo much information!!The basic protocoln Priest only maintainsn lastTried[p]: The number of the last ballot p tried toinitiated or -∞n prevVote[p]: The vote cast by p in the highest-numbered ballot in which he voted or -∞n nextBal[p]: The largest value of b for which p has senda LastVote(b,v) or -∞n A priest p initiates one ballot at a time, ballot numberlastTried[p]n Both these protocol guarantee consistency butcannot ensure progressComplete synod protocoln To achieve progress the priests do steps (2)-(6) assoon as possiblen Describes when a ballot should be initiatedn Need to know the time estimatesn 4 minutes to deliver a message within Chambern 7 minutes to perform an actionn If a single priest initiated a ballot when majority ispresent, then after step(1), if none of the priests ormessengers left the Chamber or no larger-numberedballot was previously initiated, he would executestep(3) after 22 minsThe complete protocol(cont.)n Priests were required to initiate a new ballotiffn he could not execute step(3) or step(5) in theprevious 22 minutesn he learnt that another larger-numbered ballothad already been initiated by another priestn If a single priest initiated the ballots, then theprogress condition is met – so a presidentwas chosen, who would initiate ballots whilehe is in ChamberThe multidecree parliamentn Pass a series of numbered decreesn A single president was elected, who wouldpass the ballotsn But the first two steps of the protocol areexecuted just once for all the decreesRelevance to computer scienceCorrespondence between distribute database system and Paxon parliamentState Machinen a state machine consists ofn Set of statesn Set of commandsn Set of responsesn Transition function, that assignsresponse/state pair to each command/statepairState machine approachState p State qClientcommand• Paxon Parliament protocol provides a way to implement anarbitrary state machine• law book Û machine state• passing decree Û execution of commandWeaknesses• Does not tolerate arbitrary, malicious failures• No guarantee for progress though consistency is maintained forany number of benign
View Full Document
Unlocking...