6.852: Distributed Algorithms Spring, 2008Today’s planLower Bound on Rounds[Aguilera, Toueg] proofUnivalence and BivalenceInitial bivalenceBivalence through f-1 roundsSlide 8Case 1: At least one l is 1-valentCase 2: Every l is 0-valentSlide 11Disagreement after f roundsSlide 13Early-stopping agreement algorithmsSpecial case: f = 0Slide 16k-agreementThe k-agreement problemFloodMin k-agreement algorithmFloodMin correctnessProof of Theorem 1, cont’dSlide 22Lower Bound (sketch)Lower boundLabeling nodes with executionsLabeling nodes with process namesBound on roundsColoring the nodesSperner ColoringsApplying Sperner’s LemmaApproximate Agreement problemApproximate agreement algorithm [Dolev, Lynch, Pinter, Stark, Weihl]Example: n = 4, f = 1One-round guaranteesThe complete algorithmDistributed CommitCorrectness Conditions for Commit2-Phase CommitCorrectness of 2-Phase CommitAdd a termination protocol?Complexity of 2-phase commit3-Phase Commit [Skeen]3-Phase CommitSlide 44Correctness conditions (so far)Slide 46CorrectnessComplexityPractical issues for 3-phase commitPaxos consensus algorithmNext time…6.852: Distributed AlgorithmsSpring, 2008Class 6Today’s plan•f+1-round lower bound stopping agreement.•Various other kinds of consensus problems in synchronous networks:–k-agreement–Approximate agreement–Distributed commit•Reading: [Aguilera, Toueg], [Keidar, Rajsbaum], Chapter 7 (skim 7.2)•Next: Chapter 8Lower Bound on Rounds•Theorem 1: Suppose n  f + 2. There is no n-process f-fault stopping agreement algorithm in which nonfaulty processes always decide at the end of round f.•Old proof: Suppose A exists. –Construct a chain of executions, each with at most f failures, where:•First has decision value 0, last has decision value 1.•Any two consecutive executions are indistinguishable to some process i that is nonfaulty in both. –So decisions in first and last executions are the same, contradiction.–Must fail f processes in some executions in the chain, in order to remove all the required messages, at all rounds.–Construction in book, LTTR.•Newer proof [Aguilera, Toueg]:–Uses ideas from [Fischer, Lynch, Paterson], impossibility of asynchronous consensus.[Aguilera, Toueg] proof•By contradiction. Assume A solves stopping agreement for f failures and everyone decides after exactly f rounds. •Consider only executions in which at most one process fails during each round. •Recall failure at a round allows process to miss sending any subset of the messages, or to send all but halt before changing state.•Regard vector of initial values as a 0-round execution.•Defs (adapted from [FLP]): , an execution that completes some finite number (possibly 0) of rounds, is:–0-valent, if 0 is the only decision that can occur in any execution (of the kind we consider) that extends .–1-valent, if 1 is…–Univalent, if  is either 0-valent or 1-valent (essentially decided).–Bivalent, if both decisions occur in some extensions (undecided).Univalence and Bivalence1-valent0-valent bivalent0 0 0univalent0 1 11 1 1Initial bivalence•Lemma 1: There is some 0-round execution (vector of initial values) that is bivalent. •Proof (from [FLP]):–Assume for contradiction that all 0-round executions are univalent.–000…0 is 0-valent–111…1 is 1-valent–So there must be two 0-round executions that differ in the value of just one process, i, such that one is 0-valent and the other is 1-valent.–But this is impossible, because if i fails at the start, no one else can distinguish the two 0-round executions.Bivalence through f-1 rounds•Lemma 2: For every k, 0  k  f-1, there is a bivalent k-round execution.•Proof: By induction on k.–Base: Lemma 1.–Inductive step: Assume for k, show for k+1, where k < f -1.* 0round k+11-valent 0-valent•Assume bivalent k-round execution .•Assume for contradiction that every 1-round extension of  (with at most one new failure) is univalent.•Let * be the 1-round extension of  in which no new failures occur in round k+1.•By assumption, * is univalent, WLOG 1-valent.•Since  is bivalent, there must be another 1-round extension of , 0, that is 0-valent.Bivalence through f-1 rounds•In 0, some single process i fails in round k+1, by not sending to some subset of the processes, say J = {j1, j2,…jm}.•Define a chain of (k+1)-round executions, 0, 1, 2,…, m.•Each l in this sequence is the same as 0 except that i also sends messages to j1, j2,…jl.–Adding in messages from i, one at a time.* 0round k+11-valent 0-valent•Each l is univalent, by assumption.•Since 0 is 0-valent, either:–At least one of these is 1-valent, or–All are 0-valent.Case 1: At least one l is 1-valent•Then there must be some l such that l-1 is 0-valent and l is 1-valent. •But l-1 and l differ after round k+1 only in the state of one process, jl.•We can extend both l-1 and l by simply failing jl at beginning of round k+2.–There is actually a round k+2 because we’ve assumed k < f-1, so k+2  f. •And no one left alive can tell the difference!•Contradiction for Case 1.Case 2: Every l is 0-valent •Then compare:m, in which i sends all its round k+1 messages and then fails, with * , in which i sends all its round k+1 messages and does not fail.•No other differences, since only i fails at round k+1 in m.m is 0-valent and * is 1-valent.•Extend to full f-round executions:m, by allowing no further failures,*, by failing i right after round k+1 and then allowing no further failures.•No one can tell the difference.•Contradiction for Case 2.Bivalence through f-1 rounds•So we’ve proved:•Lemma 2: For every k, 0  k  f-1, there is a bivalent k-round execution.Disagreement after f rounds•Lemma 3: There is an f-round execution in which two nonfaulty processes decide differently.•Proof:* 0 round f decide 1 decide 0–Use Lemma 2 to get a bivalent (f-1)-round execution  with  f-1 failures.–In every 1-round extension of , everyone who hasn’t failed must decide (and agree).–Let * be the 1-round extension of  in which no new failures occur in round f.–Everyone who is still alive decides after *, and they must decide the same thing. WLOG, say they decide 1.–Since  is bivalent, there must be another 1-round