Computer Science 425 Distributed Systems (Fall 2009)AcknowledgementAdministrative Give it a thoughtGive it a thoughtWhat is Consensus?Canonical Application Solve Consensus!Consensus in Synchronous Systems (Dolev&Strong )Why does the algorithm work? (Proof by contradiction)Example of Consensus: Modified Ring Election for Synchronous Systems Consensus in Asynchronous Systems Consensus in an Asynchronous SystemRecallDefinitionsDefinitionsSlide Number 17Lemma 1(show properties about events, schedules, configurations)Easier Consensus ProblemMain Goal: Show “No Consensus Protocol is totally correct in spite of one fault”Valency Definition What we will showLemma 2Lemma 2What we will show Lemma 3Lemma 3Lemma 3Lemma 3Slide Number 30Slide Number 31Slide Number 32Putting it all TogetherWhy is Consensus Important? – Why is Consensus Important? SummaryBefore you go…Computer Science 425Distributed Systems(Fall 2009)Lecture 10The Consensus ProblemPart of Section 12.5 and Paper: “Impossibility of Distributed Consensus with One Faulty Process” Fisher, Lynch, Paterson, JACM, 1985 (Sections 1-3)Acknowledgement• The slides during this semester are based on ideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative • MP1 posted September 8, Tuesday– Deadline, September 25 (Friday), 4-6pm Demonstrations– Readme Files Due on September 28 (Monday)• Email readme documentation of your MP1 to TA• HW 2 posted September 22, Tuesday– Deadline, October 6 (Tuesday), 2pm (at the beginning of the class)• HW1 grading scale and histogram postedGive it a thoughtHave you ever wondered why vendors of (distributed) software solutions always only offer solutions that promise five-9’s reliability, seven-9’s reliability, but never 100% reliability?Give it a thoughtHave you ever wondered why software vendors always only offer solutions that promise five-9’s reliability, seven-9’s reliability, but never 100% reliability?The fault does not lie with Microsoft Corp. or Apple Inc. or CiscoThe fault lies in the impossibility of consensusWhat is Consensus?• N processes• Each process p has – input variable xp(v) : initially either 0 or 1– output variable yp(d) : initially b (b=undecided)• v – single value for process p; d – decision value• A process is non-faulty in a run provided that it takes infinitely many steps, and it is faulty otherwise• Consensus problem: design a protocol so that either1. all non-faulty processes set their output variables to 02. all non-faulty processes set their output variables to 13. There is at least one initial state that leads to each outcomes 1 and 2 aboveCanonical Application • A set of servers implement a distributed database– Subset of servers participate in a particular transaction– Some of the servers may fail– Remaining servers must agree on whether to install the results of the transaction to the database or discard themSolve Consensus!• Uh, what’s the model? (assumptions!)• Assumptions: – Processes fail only by crash-stopping– Delivery channel is reliable• Synchronous system: bounds on– Message delays– Max time for each process stepe.g., multiprocessor (common clock across processors)• Asynchronous system: no such bounds!e.g., The Internet! The Web!- For a system with at most f processes crashing, the algorithm proceeds in f+1 rounds (with timeout), using basic multicast (B-multicast). - Valuesri: the set of proposed values known to process p=Piat the beginning of round r.- Initially Values0i= {} ; Values1i= {vi= xp}for round r = 1 to f+1 doB-multicast (g, Values ri)Values r+1i Valuesrion B-deliver(Vj) from some process pjValues r+1i= Values r+1i∪ Vjendendyp=di= minimum(Val ues f+1i)Consensus in Synchronous Systems (Dolev&Strong )Why does the algorithm work?(Proof by contradiction)pi{v}{}pjpk p’’ p’vv vAfter sending vto p’’, p’ crashAfter sending vto pk, p’’ crashAfter sending vto pi, pk crashNo messages arrive at pjr=1r=2r=3Example of Consensus: Modified Ring Electionfor Synchronous Systems Election: 2Election: 2, 3,4,0,1Election: 2,3Coord(4): 2Coord(4): 2,3Coord(4) 2, 3,0,1Election: 2Election: 2,3Election: 2,3,0Election: 2, 3,0,1Coord(3): 2Coord(3): 2,3Coord(3): 2,3,0Coord(3): 2, 3,0,1P1P2P3P4P0P51. P2 initiates electionP1P2P3P4P0P52. P2 receives “election”, P4 diesP1P2P3P4P0P53. P2 selects 4 and announces the resultP1P2P3P4P0P54. P2 receives “Coord”, but P4 is not includedP1P2P3P4P0P55. P2 re-initiates electionP1P2P3P4P0P56. P3 is finally electedConsensus in Asynchronous SystemsConsensus in an Asynchronous System• Messages have arbitrary delay, processes arbitrarily slow (no timeouts!)• Hence, Consensus is Impossible to achieve!– even a single failed process is enough to avoid the system from reaching agreement!• Impossibility Applies to any protocol that claims to solve consensus!• Proved in a now-famous result by Fischer, Lynch and Patterson, 1983 (FLP)– Stopped many distributed system designers dead in their tracks– A lot of claims of “reliability” vanished overnightRecall• Each process p has an internal state– program counter, registers, stack, local variables – input register xp: initially either 0 or 1– output register yp: initially b (b=undecided)• Consensus Problem: design a protocol so that either1. all non-faulty processes set their output variables to 02. all non-faulty processes set their output variables to 13. (No trivial solutions allowed)Goal: Show Impossibility of Consensus!p p’Global Message Buffersend(p’,m)receive(p’)may return null“Network”DefinitionsDefinitions• Internal State of a process p• Configuration C: = Collection of Internal States of each Process + content of global message buffer• Initial configuration:= configuration in which each process starts at an initial state and message buffer is empty• Each Event e=(p, m) consists of – receipt of a message m by a process p and– processing of message m, and– sending out of all necessary messages by p (into the global message buffer)• e(C ) = resulting configuration after event e, starting from configuration C; • Note: this event is different from the Lamport events• Schedule s: sequence of events • e.g., s=(e, e’) sequence of two events e and e’.– If s is finite, then
View Full Document
Unlocking...