DOC PREVIEW
U of I CS 425 - Multicast Communication

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 425 - Multicast Communication

Documents in this Course
Lecture 8

Lecture 8

23 pages

TIPS

TIPS

3 pages

The Grid

The Grid

41 pages

Lecture 4

Lecture 4

27 pages

Lecture 4

Lecture 4

20 pages

The Grid

The Grid

41 pages

LECTURE 5

LECTURE 5

25 pages

Multicast

Multicast

23 pages

LECTURE

LECTURE

34 pages

Load more
Download Multicast Communication
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Multicast Communication and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Multicast Communication 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?