Reliable group communication

Multicast is a popular implementation of group communication, for example, data can be replicated within database cluster with multicasts.

Ordering multicast

Let’s first look at 3 types of events:

• Send event: the event of transferring a message from a sender.
• Receive event: the event of buffering data by the receiver.
• Deliver event: the event of passing data from the buffer to the application layer by the receiver.

The order of message delivery is important as it affects the correctness of the distributed systems. There are 3 flavors of reliable multicast:

• Unordered multicast
• FIFO-ordered multicast
• Causal-ordered multicast

Also, we could have an additional constraint - the totally-ordered multicast, that can be used together with any of the 3 flavors above to form hybrid styles.

Unordered multicast

This is synchronous multicast where order of delivery by different receivers are not guaranteed to be the same. In another words, every receiver might deliver the messages in the order that they received, regardless of other receivers in the same group. For instance:

Process P1 sends m1 => then sends m2

Process P2 receives m1 then deliver m1 => then receives m2 then deliver m2 

Process P1 receives m2 then deliver m2 => then receives m1 then deliver m1

FIFO-ordered multicast

The messages are delivered in the order they are send by the sender. The receivers, therefore, are expected to deliver the messages to its application layer in this exact order with respect to each individual sender. For instance, if a process A sends m1 follows by m2, but a receiving process B receives m2 first, then it has to wait for m1 to arrive before delivering m1 followed by m2 to the application layer.

Process A sends m1 => then sends m2

Process B receives: m2 then wait for m1 => start delivering m1 then m2

By definition, this type of multicast does not care about the order of delivery between different senders. So for example:

Process A sends m1 => then sends m2

Process B sends m3 => then sends m4

Process C receives messages in order: m1,m3,m2,m4 => deliver m1,m2 => then deliver m3,m4

Process D receives messages in order: m3,m1,m2,m4 => deliver m3,m4 => then deliver m1,m2

In above example, processes C and D deliver in different order, however, they still deliver in correct sending order with respect to each sender.

Implementation

Consider a group of processes:

1. Data structure:
   • Each sender uses a variable S to count the number of messages it has multicast to the group.
   • Each receiver Pi uses a vector Pi[1…n] to maintain the sequence number of the latest message that Pi has received by processes in the group, initially these numbers are zero.
2. Updating rule:
   • Before multi-casting, the sender will put value S onto the message, then multicast to the group and increment S by 1.
   • When any receiver Pi receive a new message with sequence number S from a sender Pj, Pi checks if S = Pi[j] + 1 – If S = Pi[j] + 1, Pi will set Pi[j] = Pi[j] + 1 and deliver the message to application.
   • If S > Pi[j] + 1, it will buffer the message until the intervening messages have been delivered.

Note that we can use any implementation of B-multicast in this protocol. Moreover, if we use a reliable R-multicast primitive instead of B-multicast, then we obtain a reliable FIFO multicast.

Casual-ordered multicast

In this multicast, messages delivery must follow the causal order of the messages. For instance, a message m1 casually happens before another message m2, regardless whether they were sent from same or different senders, then the receiver will always delivered m1 before m2.

We can use vector timestamp to determine the causality of the messages.

It is easy to see that if a multicast obeys casual ordering, it will also obey FIFO ordering, i.e. if m1 were sent before m2 by the same sender, then m1 also happens-before m2. However, the reverse is not true, the multicast obeying FIFI ordering might not deliver messages by different senders with respect to their causal order.

Casual-ordered multicast is useful in some applications such as social networks, bulletin boards, comments on websites, etc. For example, when you participate in a group chat, and you send a first message

• If a friend respond to your message, then it is necessary that anyone should see your message before this friend’s response.
• However, if two friends respond concurrently, then they can be seen in any order at receivers.

Implementation

Totally-ordered multicast or atomic multicast

Totally-ordered multicast is an additional constraint that used in conjunction with other type of multicast. Total-ordered multicast ensures that all receivers in the group to deliver messages in exactly the same order, i.e. in replicated services where the replicas receive update and forward the update to every others, they need to do that in the same order. So in the example of FIFO-multicast above, both processes C and D can deliver messages in the order m1,m3,m2,m4 , which they can satisfy both FIFI and total orderings, this is called FIFO atomic multicast.

Total-ordered multicast is an application of Lamport’s logical clock. Let’s consider a group of processes where each multicasts messages to others, including itself. It’s reasonable to assume that the order of receiving messages will be in the order that the same sender send, with no lost messages.

1. When a process receives a message, it puts into a local queue according to the timestamp. If we use Lamport’s clock then the received message is lower of the acknowledgment’s.
2. the process will be removed and delivered the message at the head of the queue to its’ application layer if the message has been acknowledged by other processes. These acknowledgments will also be removed when the messaged has been delivered.

As a result, every process in the group will have the same local queue, and subsequently deliver messages in the same order.

Implementation