Home | | Distributed Systems | | Distributed Systems | Multicast Communication

Chapter: Distributed Systems - Synchronization and Replication

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Multicast Communication

Group (multicast) communication: for each of a group of processes to receive copies of the messages sent to the group, often with delivery guarantees

Multicast Communication

 

·         Group (multicast) communication: for each of a group of processes to receive copies of the messages sent to the group, often with delivery guarantees

·         The set of messages that every process of the group should receive

 

·         On the delivery ordering across the group members

 

·         Challenges

 

·         Efficiency concerns include minimizing overhead activities and increasing throughput and bandwidth utilization

 

·         Delivery guarantees ensure that operations are completed

 

·         Types of group

 

·         Static or dynamic: whether joining or leaving is considered Closed or open

 

·         A group is said to be closed if only members of the group can multicast to it. Reliable

 

·        Multicast

 

·         Simple basic multicasting (B-multicast) is sending a message to every process that is a member of a defined group

Ø B-multicast (g, m) for each process p group g, send (p, message m)

Ø On receive (m) at p: B-deliver (m) at p

Ø Reliable multicasting (R-multicast) requires these properties

 

Ø Integrity: a correct process sends a message to only a member of the group

Ø Validity: if a correct process sends a message, it will eventually be delivered

Ø Agreement: if a message is delivered to a correct process, all other correct processes in the group will deliver it

 


·        Types of message ordering

·        Three types of message ordering

 

o   FIFO (First-in, first-out) ordering: if a correct process delivers a message before another, every correct process will deliver the first message before the other

 

o   Casual ordering: any correct process that delivers the second message will deliver the previous message first

 

o   Total ordering: if a correct process delivers a message before another, any other correct process that delivers the second message will deliver the first message first

 

·        •Note that

o   FIFO ordering and casual ordering are only partial orders

o   Not all messages are sent by the same sending process

o   Some multicasts are concurrent, not able to be ordered by happened before

o   Total order demands consistency, but not a particular order

 

·        Figure 12.12 Total, FIFO and causal ordering of multicast messages

 

 

·        Notice

·     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

 

·        Note that T1 and T2 are delivered in opposite order to the physical time of message creation Bulletin board example (FIFO ordering)

 

·        A bulletin board such as Web Board at NJIT illustrates the desirability of consistency and FIFO ordering. A user can best refer to preceding messages if they are delivered in order. Message 25 in Figure 12.13 refers to message 24, and message 27 refers to message 23.

 

·        Note the further advantage that Web Board allows by permitting messages to begin threads by replying to a particular message. Thus messages do not have to be displayed in the same order they are delivered

 

 

·        Implementing total ordering

§  The normal approach to total ordering is to assign totally ordered identifiers to multicast messages, using the identifiers to make ordering decisions.

 

§  One possible implementation is to use a sequencer process to assign identifiers. See Figure 12.14. A drawback of this is that the sequencer can become a bottleneck.

 

§  An alternative is to have the processes collectively agree on identifiers. A simple algorithm is shown in Figure 12.15.



·        Each process q in group g keeps

·        Aq g: the largest agreed sequence number it has observed so far for the group g

 

·        Pq g: its own largest proposed sequence number

 

·        Algorithm for process p to multicast a message m to group g 1. B-multicasts <m, i> to g, where i is a unique identifier for m

 

·        Each process q replies to the sender p with a proposal for the message‘s agreed sequence number of Pq g :=Max(Aq g, Pq g)+1

 

·        Collects all the proposed sequence numbers and selects the largest one a as the next agreed sequence number. It then B-multicasts <i, a> to g.

 

·        Each process q in g sets Aq g := Max(Aq g, a) and attaches a to the message identified by i

 

·        Implementing casual ordering

§  Causal ordering using vector timestamps (Figure 12.16)

o   Only orders multicasts, and ignores one-to-one messages between processes

 

o   Each process updates its vector timestamp before delivering a message to maintain the count of precedent messages

 


 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.