Computer Science 425 Distributed Systems (Fall 2009)AcknowledgementAdministrativePlan for TodayReliable MulticastReliable Multicast AlgorithmReliable Multicast Algorithm (R-multicast)Ordered MulticastTotal, FIFO and Causal OrderingExample: Display From Bulletin Board ProgramFIFO-ordered multicastProviding Ordering Guarantees (FIFO)Hold-back Queue for Arrived Multicast Messages: received yet undelivered messagesImplementing FIFO Ordering (FIFO-ordered multicast)Example: FIFO MulticastCausal-ordered multicastCausal MulticastCausal Ordering using vector timestampsExample: Causal Ordering MulticastTotal-ordered multicast1st Method - Using SequencerTotal Ordering Using a Sequencer (Method 1)2nd Method - ISIS AlgorithmISIS algorithm for total ordering (Method 2)ISIS algorithm for total orderingProof of Total Order (By Contradition)SummaryComputer Science 425Distributed Systems(Fall 2009)Computer Science 425Distributed Systems(Fall 2009)Lecture 5Multicast Communication Reading: Section 12.4Klara NahrstedtAcknowledgementAcknowledgement•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 Administrative •Homework 1 posted–Deadline, September 17 (Thursday)•MP1 posted today–Deadline, September 25, FridayPlan for Today Plan for Today •Reliable Multicast•Ordered Multicast –Total ordering–Causal ordering–FIFO orderingReliable MulticastReliable Multicast•Integrity: A correct (i.e., non-faulty) process p in a group(m) delivers a multicast message m at most once.–Safety property: any message delivered is identical to the one that was sent•Validity: If a correct process multicasts (sends) message m, then it will eventually deliver m.–Guarantees liveness to the sender.–Liveness property: any message is eventually delivered to destination •Agreement: If a correct process delivers message m, then all the other correct processes in group(m) will eventually deliver m.–Property of “all or nothing.”–Validity and agreement together ensure overall liveness: if some correct process multicasts a message m, then all correct processes deliver m too.Reliable Multicast AlgorithmReliable Multicast AlgorithmR-multicastB-multicastreliable unicast“USES”“USES”Reliable Multicast Algorithm (R-multicast)Reliable Multicast Algorithm (R-multicast)IntegrityAgreementif some correct process B-multicasts a message m, then, all correct processes deliver m too. If no correct processB-multicasts m, then no correct processes deliver m.Integrity, ValidityOrdered MulticastOrdered Multicast•FIFO ordering: If a correct process issues multicast(g,m) and then multicast(g,m’), then every correct process that delivers m’ will have already delivered m.•Causal ordering: If multicast(g,m) multicast(g,m’) then any correct process that delivers m’ will have already delivered m.•Total ordering: If a correct process delivers message m before m’, then any other correct process that delivers m’ will have already delivered m.Total, FIFO and Causal OrderingTotal, FIFO and Causal OrderingF3F1F2T2T1P1P2P3TimeC3C1C2•Totally ordered messages T1 and T2.•FIFO-related messages F1 and F2.•Causally-related messages C1 and C3• Causal ordering implies FIFO ordering• Total ordering does not imply causal ordering. • Causal ordering does not imply total ordering.• Hybrid mode: causal-total ordering, FIFO-total ordering.Totally-orderedFIFO-orderedCausal-orderedExample: Display From Bulletin Board ProgramExample: Display 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: MachendWhat is the most appropriate ordering for this application?(a) FIFO (b) causal (c) totalPost to Bulletin BoardUser 1Post to Bulletin BoardUser 2FIFO-ORDERED MULTICASTFIFO-ORDERED MULTICAST Process messages from each process in the order they were sent:Each process keeps a sequence number for each other process. Messages are sent with local sequence number When a message is received, as expected (next sequence), accepthigher than expected, buffer in a queue lower than expected, rejectProviding Ordering Guarantees (FIFO) Providing Ordering Guarantees (FIFO) If Message# isHold-back Queue for Arrived Multicast Messages: received yet undelivered messagesHold-back Queue for Arrived Multicast Messages: received yet undelivered messagesMessageprocessingDelivery queueHold-backqueuedeliverIncomingmessagesWhen delivery guarantees aremetFO-deliverImplementing FIFO Ordering (FIFO-ordered multicast)Implementing FIFO Ordering (FIFO-ordered multicast)•Spg: count of messages p has sent to g.•Rqg: the recorded sequence number of the latest message that p has delivered from q to the group g. •For p to FO-multicast m to g–p increments Spg by 1 –p “piggy-backs” the value Spg onto the message.–p B-multicasts m to g.•At process p, upon receipt of m from q with sequence number S:–p checks whether S= Rqg+1. If so, p FO-delivers m and increments Rqg–If S > Rqg+1, p places the message in the hold-back queue until the intervening messages have been delivered and S= Rqg+1.–If S < Rqg+1, then drop the message (we have already seen the message)Example: FIFO Multicast Example: FIFO Multicast P1P2P30 0 0Physical Time1 0 02 0 01 0 02 0 02 1 02 1 00 0 00 0 02 1 00 0 0 1 0 02 1 01112211Reject: 1 < 1 + 1Accept 1 = 0 + 1Accept: 2 = 1 + 12 0 0Buffer 2 > 0 + 1Accept: 1 = 0 + 12 0 0Accept Buffer 2 = 1 + 1Reject: 1 < 1 + 1Accept 1 = 0 + 1Sequence Vector for P1(do NOT confuse with vector timestamps)0 0 0S1gR2gR3g0 0 0R1gS2gR3gSequence Vector for P2CAUSAL-ORDERED MULTICASTCAUSAL-ORDERED MULTICASTCausal MulticastCausal Multicast•Let us focus on multicast group g•Each process iєg maintains a vector Vgi of length |g| where–Vgi[j] counts the number of group g messages from j to i•Messages multicast by process i are tagged with the vector timestamp Vgi•Recall rule for receiving vector timestamps Max(Vreceiver[j] , Vmessage[j]), if j is not self Vreceiver[j] + 1 otherwise•i.e. when process i receives a <m,Vgj> from j, then –Vgi[k] = max(Vgi[k], Vgj[k]) if k ≠ i–Vgi[k] = Vgi[k]
View Full Document