6.852: Distributed Algorithms Fall, 2009Today’s planLower Bound on Rounds[Aguilera, Toueg] proofUnivalence and BivalenceInitial bivalenceBivalence through f-1 roundsBivalence through f-1 roundsCase 1: At least one l is 1-valentCase 2: Every l is 0-valent Bivalence through f-1 roundsDisagreement after f roundsDisagreement after f roundsEarly-stopping agreement algorithmsJust consider special case: f = 0Special case: f = 0k-Agreementk-agreementThe k-agreement problemFloodMin k-agreement algorithm FloodMin correctnessProof of Theorem 1, cont’dProof of Theorem 1, cont’dLower Bound (sketch)Lower boundLabeling nodes with executionsLabeling nodes with process namesBound on roundsColoring the nodesSperner ColoringsApplying Sperner’s LemmaApproximate AgreementApproximate Agreement problemApproximate agreement algorithm [Dolev, Lynch, Pinter, Stark, Weihl]Example: n = 4, f = 1One-round guaranteesThe complete algorithmDistributed CommitDistributed CommitCorrectness Conditions for Commit2-Phase CommitCorrectness of 2-Phase CommitAdd a termination protocol?Complexity of 2-phase commit3-Phase Commit [Skeen]3-Phase Commit3-Phase CommitCorrectness conditions (so far)3-Phase CommitCorrectnessComplexityPractical issues for 3-phase commitPaxos consensus algorithmNext time…6.852: Distributed AlgorithmsFall, 2009Class 6Today’s plan• f+1-round lower bound for stopping agreement, cont’d.• Various other kinds of consensus problems in synchronous networks:– k-agreement– Approximate agreement (skip)– Distributed commit• Reading: – [Aguilera, Toueg]– [Keidar, Rajsbaum]– Chapter 7 (skip 7.2)• Next: – Modeling asynchronous systems– Chapter 8Lower Bound on Rounds• Theorem 1: Suppose n ≥ f + 2. There is no n-process f-fault stopping agreement algorithm in which nonfaultyprocesses 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 0α univalentα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, say i, fails in round k+1, by not sending to some set of 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 αldiffer after round k+1 only in the state of one process, jl.• We can extend both αl-1 and αl by simply failing jlat 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 αlis 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.• αmis 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, so far:• 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:αα* α0round fdecide 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