How can one get around FLP?Weaken the problemWeaken terminationuse randomization to terminate with probability 1Weaken agreementε - agreementreal-valued inputs and outputsagreement within real-valued small positive tolerance εk-set agreementAgreement: In any execution, there is a subset W of the set of input values, |W| =k, s.t. all decision values are in WValidity: In any execution, any decision value for any process is the input value of some processHow can one get around FLP?Constrain input valuesCharacterize the set of input values for which agreement is possibleStrengthen the system modelIntroduce failure detectors to distinguish between crashed processes and very slow processesThe Part-Time ParliamentParliament determines laws by passing sequence of numbered decreesLegislators can leave and enter the chamber at arbitrary timesNo centralized record of approved decrees–instead, each legislator carries a ledgerGovernment 101No two ledgers contain contradictory informationIf a majority of legislators were in the Chamber and no one entered or left the Chamber for a sufficiently long time, then any decree proposed by a legislator would eventually be passedany passed decree would appear on the ledger of every legislatorSuppliesEach legislator receives ledgerpen with indelible inkscratch paperhourglasslots of messengersBack to the futureA set of processes that can propose valuesProcesses can crash and recoverProcesses have access to stable storageAsynchronous communication via messagesMessages can be lost and duplicated, but not corruptedThe Game: ConsensusSAFETYOnly a value that has been proposed can be chosenOnly a single value is chosenA process never learns that a value has been chosen unless it has beenLIVENESSSome proposed value is eventually chosenIf a value is chosen, a process eventually learns itThe PlayersProposersAcceptorsLearnersChoosing a valueHave a single acceptorChoosing a valueHave a single acceptorsmajority ofUsing a majority set guarantees that at most one value is chosenAccepting a valueSuppose only one proposer proposes a single value assume no failuresthat value should be accepted!Accepting a valueSuppose only one proposer proposes a single value assume no failuresthat value should be accepted!P1: Acceptors must accept first received proposalAccepting a valueChoosing a value requires a majority of acceptors to accept that valueWhat if we have multiple proposers, each proposing a different value?Acceptors must accept multiple proposals (each identified by pair (n, value))Multiple proposals may be chosen!P1: Acceptors must accept first received proposal?Guaranteeing uniquenessP2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value vHow do we implement P2? What about: If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value vA proposal may be chosen before an acceptor gets to accept its first value...Another take on P2If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value vAnother take on P2If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value vIf a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value vImplementing P2Achieved by enforcing the following invariantFor any v and n, if a proposal with value v and sequence number n is issued, then there is a majority-set S of acceptors such that one of the following holds:no acceptor in S has accepted any proposal numbered less than nv is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in SIf a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value vThe protocol:phase 1A proposer chooses a new n and sends <prepare,n> to a majority of acceptorsIf an acceptor a receives <prepare,n’>, where n’ > n for any <prepare,n> to which a has responded, then it responds to <prepare,m> with a promise not to accept any more proposals numbered less than mthe highest numbered proposal (if any) that it has acceptedThe protocol:phase 2If the proposer receives a response to <prepare,n> from a majority of acceptors, then it sends to each <accept,n,v>, where v is eitherthe value of the highest numbered proposal among the responsesany value if the responses reported no proposalsIf an acceptor receives <accept,n,v>, it accepts the proposal unless it has in the meantime responded to <prepare,n’> , where n’ > nLearning chosen valuesOnce a value is chosen, it is forwarded to the learners. Many strategies are possible:i. Each acceptor informs each learnerii. Acceptors inform a distinguished learner, who informs the other learnersiii. Something in betweenLivenessProgress is not guaranteed:n1 < n2 < n3 < n4 < …p1<propose,n1><accept(n1,v1)><propose,n3>p2<propose,n2><accept(n2,v2)><propose,n4>TimeAll proposers are equal, but some more so than othersElect a distinguished proposerCan’t be done reliably in asynchronous systems, so…randomizationfailure detectorsThe Triumph of RandomizationThe Big PictureDoes randomization make for more powerful algorithms?Does randomization expand the class of problems solvable in polynomial time?Does randomization help compute problems fast in parallel in the PRAM model? You tell me!The Triumph of RandomizationWell, at least for distributed computations!no deterministic 1-crash-resilient solution to Consensus resilient randomized solution to consensus ( ) for crash failuresrandomized solution for Consensus exists even for Byzantine failures!ff <n/2A simple randomized algorithmM. Ben Or. “Another advantage of free choice: completely asynchronous agreement protocols” (PODC 1983, pp. 27-30)exponential number of operations per processBUT more practical protocols exist down to expected operations/process resilientO(n log2n)n− 1The protocol’s structureAn infinite repetition of asynchronous roundsin round , only handles messages with timestamp each round has two phasesin the first, each broadcasts an a-value which is a function of the b-values collected in the previous round (the first a-value is the input bit)in the second, each broadcasts a b-value which is a function of the collected a-values decide stuttersrprppBen Or’s Algorithm 1: := input bit; := 1; 2: repeat forever 3:
View Full Document
Unlocking...