6.852: Distributed Algorithms Fall, 2009Today’s planDistributed consensusConsensus with link failuresFormal problem statementAlternatively:Impossibility for 2 Generals [Gray]2-Generals ImpossibilityA fine point:Continuing…The contradictionConsensus with process failuresStopping agreementByzantine agreementTechnicality about stopping vs. Byzantine agreementComplexity measuresSimple algorithm for stopping agreementHow many rounds?Correctness proof (for k = f+1)Check correctness conditionsComplexity boundsImproved algorithm (Opt)CorrectnessProof of correspondenceExponential Information Gathering (EIG)EIG Stopping agreement algorithmExampleExampleExampleCorrectness and complexityByzantine agreement algorithmBad example: n = 3, f = 1Bad exampleBad exampleBad exampleNotes on the exampleEIG algorithm for Byzantine agreementExample: n = 4, f = 1Example: n = 4, f = 1Correctness proofProof, cont’dMain correctness conditionsAgreementAgreementAgreementComplexity boundsNext time…6.852: Distributed AlgorithmsFall, 2009Class 4Today’s plan• Fault-tolerant consensus in synchronous systems• Link failures:– The Two Generals problem• Process failures:– Stopping and Byzantine failure models– Algorithms for agreement with stopping and Byzantine failures– Exponential information gathering• Reading: Section 5.1, 6.1-6.3• Next: – Lower bounds for Byzantine agreement:• Number of processors• Number of rounds– Reading:• Sections 6.4-6.7• [Aguilera, Toueg]• (Optional) [Keidar-Rajsbaum]Distributed consensus• Abstract problem of reaching agreement among processes in a distributed system, all of which start with their own “opinions”.• Complications: Failures (process, link); timing uncertainties.• Motivation:– Database transactions: Commit or abort– Aircraft control:• Agree on value of altimeter reading (SIFT)• Agree on which plane should go up/down, in resolving encounters (TCAS)– Resource allocation: Agree on who gets priority for obtaining a resource, doing the next database update, etc.– Replicated state machines: To emulate a virtual machine consistently, agree on next step.• Fundamental problem• We’ll revisit it several times:– In synchronous, asynchronous, and partially synchronous settings.– With link failures, processor failures.– Algorithms, impossibility results.Consensus with link failures• Informal scenario:– Several generals plan a coordinated attack.– All should agree to attack:• Absolutely must agree.• Should attack if possible.– Each has an initial opinion about his army’s readiness.– Nearby generals can communicate using foot messengers:• Unreliable, can get lost or captured• Connected, undirected communication graph, known to all generals, known bound on time for successful messenger to deliver message. • Motivation: Transaction commit• Can show no algorithm exists!Formal problem statement• G = (V,E), undirected graph (bidirected edges)• Synchronous model, n processes• Each process has input 1 (attack) or 0 (don’t attack).• Any subset of the messages can be lost.• All should eventually set decision output variables to 0 or 1.– In practice, would need this by some deadline.• Correctness conditions:– Agreement: • No two processes decide differently.– Validity:• If all start with 0, then 0 is the only allowed decision.• If all start with 1 and all messages are successfully delivered, then 1 is the only allowed decision.Alternatively:• Stronger validity condition:– If anyone starts with 0 then 0 is the only allowed decision.– If all start with 1 and all messages are successfully delivered, then 1 is the only allowed decision.– Typical for transaction commit (1 = commit, 0 = abort).• Guidelines: – For designing algorithms, try to use stronger correctness conditions (better algorithm).– For impossibility results, use weaker conditions (better impossibility result).Impossibility for 2 Generals [Gray]• Other cases similar, LTTR.• Proof: By contradiction.– Suppose we have a solution---a process (states, transitions) for each index 1, 2.– Assume WLOG that both processes send messages at every round.• Could add dummy messages.– Proof based on limitations of local knowledge.– Start with α, the execution where both start with 1 and all messages are received.• By the termination condition, both eventually decide.• Say, by the end of r rounds.• By the validity condition, both decide on 1.2-Generals Impossibility• α1: Same as α, but lose all messages after round r.– Doesn’t matter, since they’ve already decided by round r.– So, both decide 1 in α1.•.α2: Same as α1, but lose the last message from process 1 to process 2.–Claim α1 is indistinguishable from α2 by process 1, α1 ∼1α2.– Formally, 1 sees the same sequence of states, incoming and outgoing messages.– So process 1 also decides 1 in α2.– By termination, process 2 decides in α2.– By agreement, process 2 decides 1 in α2.Process 1 Process 2Rd 1Rd r-1Rd rRd 2Rd 3A fine point:•In α2 , process 2 must decide 1 at some point, not necessarily by round r.Continuing…• α3: Same as α2, but lose the last message from process 2 to process 1.– Then α2 ∼2α3.– So process 2 decides 1 in α3.– By termination, process 1 decides in α3.– By agreement, process 1 decides 1 in α3.• α4: Same as α3, but lose the last message from process 1 to process 2.– Then α3 ∼1α4.– So process 1 decides 1 in α4.– So process 2 decides 1 in α4.• Keep removing edges, get to:Process 1 Process 2Rd 1Rd r-1Rd rRd 2Rd 3The contradiction• α2r+1: Both start with 1, no messages received.– Still both must eventually decide 1.• α2r+2: process 1 starts with 1, process 2 starts with 0, no messages received.– Then α2r+1 ∼1α2r+2.– So process 1 decides 1 in α2r+2.– So process 2 decides 1 in α2r+2.• α2r+3: Both start with 0, no messages received. – Then α2r+2 ∼2α2r+3.– So process 2 decides 1 in α2r+3.– So process 1 decides 1 in α2r+3.•But α2r+3contradicts weak validity!Consensus with process failures• Stopping failures (crashes) and Byzantine failures (arbitrary processor malfunction, possibly malicious)• Agreement problem:– n-node connected, undirected graph, known to all processes.– Input v from a set V, in some state variable.– Output v from V, by setting decision := v.– Bounded number ≤ f of