Computer Science 425 Distributed Systems CS 425 / CSE 424 / ECE 428 Fall 2010Communication Modes in DSSlide 3Other Examples of Multicast UseWhat’re we designing in this classBasic Multicast (B-multicast)Reliable MulticastReliable R-Multicast AlgorithmReliable Multicast Algorithm (R-multicast)Ordered MulticastTotal, FIFO and Causal OrderingDisplay From Bulletin Board ProgramProviding Ordering Guarantees (FIFO)Implementing FIFO OrderingHold-back Queue for Arrived Multicast MessagesExample: FIFO MulticastTotal Ordering Using a SequencerISIS algorithm for total orderingSlide 19Proof of Total OrderCausal Ordering using vector timestampsExample: Causal Ordering MulticastSummaryLecture 7-1Lecture 7-1Computer Science 425Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 2010Computer Science 425Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 2010Indranil Gupta (Indy)September 14, 2010Lecture 7MulticastReading: Sections 12.4 2010, I. Gupta, K. Nahrtstedt, S. Mitra, N. Vaidya, M. T. Harandi, J. HouLecture 7-2Lecture 7-2Communication Modes in DS Communication Modes in DS Unicast (best effort or reliable) Messages are sent from exactly one process to one process. Best effort guarantees that if a message is delivered it would be intact. Reliable guarantees delivery of messages. Broadcast Messages are sent from exactly one process to all processes on the network. Broadcast protocols are not practical. Multicast Messages broadcast within a group of processes. Messages are sent from exactly one process to several processes on the network. Reliable multicast can be implemented “above” (i.e., “using”) a reliable unicast. This lecture!Lecture 7-3Lecture 7-3Lecture 7-4Lecture 7-4Other Examples of Multicast Use Other Examples of Multicast Use •Akamai’s Configuration Management System (called ACMS) uses a core group of 3-5 servers. These servers continuously multicast to each other the latest updates. They use reliable multicast. After an update is reliably multicast within this group, it is then sent out to all the (1000s of) servers Akamai has all over the world.•Air Traffic Control System: orders by one ATC need to be ordered (and reliable) multicast out to other ATC’s.•Newsgroup servers multicast to each other in a reliable and ordered manner.Lecture 7-5Lecture 7-5What’re we designing in this classWhat’re we designing in this classApplication(at process p)MULTICAST PROTOCOLsend multicast Incomingmessagesdelivermulticast One process pLecture 7-6Lecture 7-6Basic Multicast (B-multicast)Basic Multicast (B-multicast)•A straightforward way to implement B-multicast is to use a reliable one-to-one send (unicast) operation:–B-multicast(g,m): for each process p in g, send (p,m).–receive(m): B-deliver(m) at p.•A “correct” process= a “non-faulty” process•A basic multicast primitive guarantees a correct (i.e., non-faulty) process will eventually deliver the message, as long as the sender (multicasting process) does not crash.–Can we provide reliability even when the sender crashes (after it has sent the multicast)?Lecture 7-7Lecture 7-7Reliable MulticastReliable Multicast•Integrity: A correct (i.e., non-faulty) process p delivers a message m at most once.•Validity: If a correct process multicasts (sends) message m, then it will eventually deliver m itself.–Guarantees liveness to the sender.•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.Lecture 7-8Lecture 7-8Reliable R-Multicast AlgorithmReliable R-Multicast AlgorithmR-multicastB-multicastreliable unicast“USES”“USES”Lecture 7-9Lecture 7-9Reliable Multicast Algorithm (R-multicast)Reliable Multicast Algorithm (R-multicast)IntegrityAgreementif some correct process B-multicasts a message m, then, all correct processes R-deliver m too. If no correct processB-multicasts m, then no correct processes R-deliver m.Integrity, ValidityLecture 7-10Lecture 7-10Ordered 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’ (independent of the senders), then any other correct process that delivers m’ will have already delivered m.Lecture 7-11Lecture 7-11Total, 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.Lecture 7-12Lecture 7-12Display From Bulletin Board ProgramDisplay 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) totalLecture 7-13Lecture 7-13 Look at messages from each process in the order they were sent:Each process keeps a sequence number for each other process. 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# isLecture 7-14Lecture 7-14Implementing FIFO OrderingImplementing FIFO Ordering•Spg: the number of messages p has sent to g.•Rqg: the sequence number of the latest group-g message p has delivered from q. •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.Lecture 7-15Lecture
View Full Document
Unlocking...