Distributed Computing Wikiclass | Lecture / Multicast and Group Communications

A Distributed Computing Lecture by Steven Choy

Introduction and Design Issues of Group Communication

Group communication refers to the ability of a set of more than two processes in a communication network to communicate with each other.
Multicast communication refers to a process sending a message to all members of the group of processes.
Group communication services are important building blocks for many useful distributed applications that require fault-tolerant, high-performance, and high-availability characteristics.
There are six important issues that need to be addressed in the design of group communication within a distributed system.
Addressing methods for a group of members

The simplest one is to require the sender to explicitly specify all the destinations to which the message should be delivered. A second method is to use a single address for the whole group. This method saves bandwidth and also allows a process to send a message without knowing which processes are members of the group.

Reliability: whether the communication is reliable or unreliable

‘The second design criterion, reliability, deals with recovery from communication failures, such as buffer overflows and garbled packets. Because reliability is more difficult to implement for group communication than for point-to-point communication, a number of existing operating systems provided unreliable group communication, whereas almost all operating systems provide reliable point-to-point communication, for example, in the form of RPC.’

Ordering : the order among messages in the communication

‘Another important design decision in group communication is the ordering of messages sent to a group. Roughly speaking, there are 4 possible orderings: no ordering, FIFO ordering, causal ordering, and total ordering.

Delivery semantics: how many group members must receive the message successfully

‘The fourth item, delivery semantics relates to when a message is considered delivered successfully to a group. There are 3 choices: k-delivery, quorum delivery, and atomic delivery. With k-delivery, a broadcast is successful when k processes have received the message for some constant k. With quorum delivery, a broadcast is defined as being successful when a majority of the current membership has received it. With atomic delivery either all processes receive it or none do. For many applications atomic delivery is the ideal semantics, but is harder to implement if processors can fail.’

Response semantics: how to response to a broadcast message
Group structure: about the semantics of a group such as dynamic versus static and open versus closed

‘The last design decision specific to group communication is group structure. Groups can be either closed or open. In a closed group, only members can send messages to the group. In an open group, nonmembers may also send messages to the group. In addition, groups can be static or dynamic. In static groups processes cannot leave or join a group, but remain a member of the group for the lifetime of the process. Dynamic groups may have a varying number of members over time.’

References: Kaashoek, M F (1993) ‘Group Communication in Amoeba and its Applications’, Distributed System Engineering, 1:9, 48–58.

Applications of Group Communications

Multicast messages provides a useful infrastructure for constructing distributed systems with the following characteristics:
Fault tolerance based on replicated services: A replicated service consists of a group of servers. Client requests are multicast to all the members of the group, each of which performs an identical operation. Even when some of the members fail, clients can still be served.
Finding the discovery servers in spontaneous networking: Multicast messages can be used by servers and clients to locate available discovery services in order to register their interfaces or to look up the interfaces of other services in the distributed system.
Better performance through replicated data: Data are replicated to increase the performance of a service - in some cases replicas of the data are placed in users' computer. Each time the data changes, the new values is multicast to the processes managing the replicas.
Propagation of event notifications: Multicast to a group may be used to notify processes when something happens. For example, a news system might notify interested users when a new message has been posted on a particular newsgroup.
References: Chapter 4: Interprocess Communication in 'Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edition 4 (the website for the book is http://www.cdk4.net/).

Mutlicast group

In an application or network service which makes use of multicasting, a set of processes form a group, called a multicast group.
Each process in a group can send and receive message.
A message sent by any process in the group can be received by each participating process in the group.
A process may also choose to leave a multicast group.
Primitive operations

Join – allows a process to join a specific multicast group

Leave – allows a process to stop participating in a multicast group

Send – allows a process to send a message to all processes currently participating in a multicast group

Receive – allows a member process to receive messages sent to a multicast group

Basic multicast and Atomic multicast

Three criteria
- Liveness - Each process must receive every message
- Integrity - No spurious message received
- No duplicate - Accepts exactly one copy of a message
A multicast is atomic, when the message is delivered to every correct member, or to no member at all.
Basic multicast does not consider failures. Reliable multicast handles failures.

Reliable and Unreliable Multicast

Unreliable multicast: a multicast system will make a good-faith attempt to deliver messages to each participating process, but the arrival of the correct message at each process is not guaranteed
Reliable multicast: a multicast system which guarantees that each message is eventually delivered to each process in the group
The definition of reliable multicast requires that each participating process receives exactly one copy of each message sent. However, the definition places no restriction on the order that the messages are delivered to each process.
We can further classify reliable multicast systems based on the order of the delivery of messages.

Ordering of reliable multicast

FIFO ordering: If a correct process issues multicast(g,m) and then multicast(g,m'), then every correct process that delivers m' will deliver m before m'.

Messages are delivered in the order they were sent by any single sender (First-in-first-out or sender ordered multicast)

Local order (a.k.a. Single source FIFO) - Example: video distribution, distance learning using “push technology.”

Causal ordering: If multicast(g,m) → multicast(g,m'), where → is the happened-before relation induced only by messages sent between the members of g, then any correct process that delivers m' will deliver m before m'.

Causal ordering: If Send( M1 ) → Send( M2 ), then the receipient should receive M1 before M2.

Causal order multicast - If a, b are two updates and a happened before b, then every member must accept a before accepting b. Example: implementation of a bulletin board.

Total ordering: If a correct process delivers message m before it delivers m', then any other correct process that delivers m' will deliver m before m'.

Messages are delivered in same order to all recipients.

Total order multicast - Every member must receive all updates in the same order. Example: consistent update of replicated data on servers

Causal ordering implies FIFO ordering, since any two multicasts by the same process are related by happened-before.
References: Chapter 12: Coordination and Agreement in 'Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edition 4 (the website for the book is http://www.cdk4.net/).

Implementing Causal Ordering

We can detect a causality violation using vector timestamps by comparing the timestamp of a newly received message to the local time. If the message's timestamp is less than the local time vector, a causality violation has occurred.

(Source: Coulouris, Dollimore and Kindberg, Distributed Systems: Concepts and Design Edition 4)

Example

More Example: An example from that web page.

Implementing total order multicast

Step 1. Sender i sends (m, ts) to all
Step 2. Receiver j saves it in a holdback queue, and sends an ack (a, ts)
Step 3. Receive all acks, and pick the largest ts. Then send (m, ts, commit) to all.
Step 4. Receiver removes it from the holdback queue and delivers m in the ascending order of timestamps.
Example

Java Multicast API

Multicast - receiving data

import sun.net.*;

import java.net.*;

int port = 5000;

String group = "225.4.5.6";

MulticastSocket s = new MulticastSocket(port);

s.joinGroup(InetAddress.getByName(group));

byte buf[] = byte[1024];

DatagramPacket pack = new DatagramPacket(buf, buf.length);

s.receive(pack);

System.out.println("Received data from: " + pack.getAddress().toString() +

        ":" + pack.getPort() + " with length: " +

        pack.getLength());

System.out.write(pack.getData(),0,pack.getLength());

System.out.println();

s.leaveGroup(InetAddress.getByName(group));

s.close();

[Get Code]

Multicast - sending data

import sun.net.*;

import java.net.*;

int port = 5000;

String group = "225.4.5.6";

int ttl = 1;

MulticastSocket s = new MulticastSocket();

// We don't have to join the multicast group if we are only

// sending data and not receiving

byte buf[] = byte[10];

for (int i=0; i<buf.length; i++) buf[i] = (byte)i;

DatagramPacket pack = new DatagramPacket(buf, buf.length,

                                         InetAddress.getByName(group), port);

s.send(pack,(byte)ttl);

s.close();

[Get Code]

Class Exercises

Ordering is an important issue that needs to be addressed in the design of multicast group communication. Briefly describe the four possible orderings of group communication.

Consider the following example of multicast communication. A multicast group G has five member processes, A, B, C, D and E. Process A multicasts messages a1 then a2 to group G. Process B multicast message b1 and then b2 to group G. Process B multicasts b1 and b2 after delivering a1. Process B then deliveries a2 after multicasting b1 and b2.

Processes C, D, and E may deliver these four messages (a1, a2, b1, b2) in different order. It is based on the ordering requirement implemented by the group.

Consider that group G implements FIFO ordering. Write all possible sequences of messages as delivered by process C.
Consider that group G implements causal ordering. Write all possible sequences of messages as delivered by process C.
Does causal ordering imply FIFO ordering?
Consider that group G implements total ordering. For each of the processes C, D, and E, write a possible sequence of messages delivered.
Briefly describe the methods used to implement causal orderings in a non-overlapping group.

Consider the following example of multicast communication. A multicast group G has three member processes, P1, P2, and P3. Process P2 multicasts messages m1 and then m3 to group G. Process P3 multicast message m2 to group G. Process P3 multicasts m2 after delivering m1. Processes P1, P2, and P3 may deliver the three messages (m1, m2, m3) in different order. It is based on the ordering requirement implemented by the multicast group.

Consider that group G implements FIFO ordering. Write all possible sequences of messages as delivered by process P1.
Consider that group G implements FIFO ordering. Write all possible sequences of messages as delivered by process P2.
Consider that group G implements causal ordering. Write all possible sequences of messages as delivered by process P1.

Extra Materials

Thanks for Reading

If you would rather like to have this lecture note in printed format, please click the print action link in the top right corner.

If you find any problem in this lecture note, please feel free to reach Steven by steven@findaway.hk