· 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
· 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
· 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
· 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
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.