Slides for Chapter 12: Coordination and AgreementFigure 12.1 A network partitionAgreement in Pepperland (p.51)Consensus in the presence of failure (p.54)Consensus in Space Mission LaunchesShuttle StoryFigure 12.2 Server managing a mutual exclusion token for a set of processesFigure 12.3 A ring of processes transferring a mutual exclusion tokenFigure 12.4 Ricart and Agrawala’s algorithmFigure 12.17 P.500 Consensus for three processesFailure Management in Web-services world – WS-membershipSlides for Chapter 12: Coordination and AgreementFrom Coulouris, Dollimore and KindbergDistributed Systems: Concepts and DesignEdition 4, © Pearson Education 2005Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005 Figure 12.1A network partitionCrashedrouterAgreement in Pepperland (p.51)Consider an army in Pepperland: Apples and Oranges: two groups are located on the hillsBlue Meanies are invader. Now located in the valley.Apple and Orange have to decide when to attack.They exchange messages on their strength: number of attack items (personal, machinery etc).They reach a consensus on who will attack first based on strength.Then attack message is sent from stronger team to weaker team. The message delay {min… max}Apple (say) send the attack message, waits for min minutes; then starts attack; Other team is supposed to wait for 1 min after it receives attack msg;Ideal guarantee: Orange will start attack no more than {max-min+1} minutes.Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005Consensus in the presence of failure (p.54)How do you detect failure? What if the messenger from Apple to Orange is captured?How does Orange know if Apple has been defeated?Impossibility in reaching agreement in the presence of failures: to surrender or to attack?If the messenger is captured there is way to achieve agreement.Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005Consensus in Space Mission LaunchesMission critical applicationsSet of divisions each in charge of a module of the (shuttle) missionThey have to agree or come to a consensus to launch (attack in Pepperland) or abort (surrender in Pepperland).In case of failure of message, consensus is reached to abort the mission.Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005Shuttle Story“I had a friend who was one of the programmers who worked on the Shuttle guidance system, which used three computers in parallel, and operated under a consensus model. If two computers agreed on a decision, the third would remain quiescent. If they disagreed, however, the third computer would jump in to cast a tie-breaking vote. I asked what would happen if the three computers came up with three different answers, and he shook his head. I asked what would happen if one of those computers dropped out, and he said the other two would end up dead-locked.” Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005 Figure 12.2Server managing a mutual exclusion token for a set of processesServer1. RequesttokenQueue ofrequests2. Releasetoken3. Granttoken42p4p3p2p1Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005 Figure 12.3A ring of processes transferring a mutual exclusion tokenpnp2p3p4Tokenp1Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005 Figure 12.4Ricart and Agrawala’s algorithmOn initializationstate := RELEASED; To enter the sectionstate := WANTED;Multicast request to all processes; request processing deferred hereT := request’s timestamp;Wait until (number of replies received = (N – 1));state := HELD;On receipt of a request <Ti, pi> at pj (i ≠ j)if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi)))then queue request from pi without replying; else reply immediately to pi;end ifTo exit the critical sectionstate := RELEASED;reply to any queued requests;Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education 2005 Figure 12.17 P.500Consensus for three processes1P2P3 (crashes)P1Consensus algorithmv1=proceedv3=abortv2=proceedd1:=proceed d2:=proceedFailure Management in Web-services world – WS-membershipSee the next presentationInstructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Pearson Education