Multicast Communication

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