Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20From Coulouris, Dollimore, Kindberg and BlairDistributed Systems: Concepts and DesignEdition 5, © Addison-Wesley 2012 Slides for Chapter 15: Coordination and AgreementInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.1A network partitionCrashedrouterInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.2Server managing a mutual exclusion token for a set of processesServer1. RequesttokenQueue ofrequests2. Releasetoken3. Granttoken42p4p3p2p1Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.3A ring of processes transferring a mutual exclusion tokenpnp2p3p4Tokenp1Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.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, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.5Multicast synchronizationp334Reply3441414134p1p2ReplyReplyInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.6Maekawa’s algorithm – part 1On initializationstate := RELEASED;voted := FALSE;For pi to enter the critical sectionstate := WANTED;Multicast request to all processes in Vi;Wait until (number of replies received = K);state := HELD;On receipt of a request from pi at pjif (state = HELD or voted = TRUE)then queue request from pi without replying; else send reply to pi;voted := TRUE;end ifFor pi to exit the critical sectionstate := RELEASED;Multicast release to all processes in Vi;On receipt of a release from pi at pjif (queue of requests is non-empty)then remove head of queue – from pk, say; send reply to pk;voted := TRUE;else voted := FALSE;end ifInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.7A ring-based election in progress24159432817241Note: The election was started by process 17.The highest process identifier encountered so far is 24. Participant processes are shown in a darker colourInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.8The bully algorithmp1p2p3p4p1p2p3p4CcoordinatorStage 4CelectionelectionStage 2p1p2p3p4CelectionansweranswerelectionStage 1timeoutStage 3Eventually.....p1p2p3p4electionanswerThe election of coordinator p2, after the failure of p4 and then p3Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.9Reliable multicast algorithmInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.10The hold-back queue for arriving multicast messagesMessageprocessingDelivery queueHold-backqueuedeliverIncomingmessagesWhen delivery guarantees aremetInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.11Total, FIFO and causal ordering of multicast messagesF3F1F2T2T1P1P2P3TimeC3C1C2Notice the consistent ordering of totally ordered messages T1 and T2, the FIFO-related messages F1 and F2 and the causally related messages C1 and C3 – and the otherwise arbitrary delivery ordering of messages.Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.12Display from bulletin board programBulletin board: os.interestingItemFrom Subject23 A.Hanlon Mach 24 G.Joseph Microkernels25 A.Hanlon Re: Microkernels26 T.L’Heureux RPC performance27 M.Walker Re: MachendInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.13Total ordering using a sequencerInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.14The ISIS algorithm for total ordering211221 Message2 Proposed SeqP2P3P1P43 Agreed Seq33Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.15Causal ordering using vector timestampsInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.16Consensus for three processes1P2P3 (crashes)P1Consensus algorithmv1=proceedv3=abortv2=proceedd1:=proceed d2:=proceedInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.17Consensus in a synchronous systemInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.18Three Byzantine generalsp1 (Commander)p2p31:v1:v2:1:v3:1:up1 (Commander)p2p31:x1:w2:1:w3:1:xFaulty processes are shown colouredInstructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5 © Pearson Education 2012 Figure 15.19Four Byzantine generalsp1 (Commander)p2p31:v1:v2:1:v3:1:uFaulty processes are shown colouredp41:v4:1:v2:1:v