Dynamic Group Communication
Dynamic Group Communication
Aaron Pettit
Abstract
This report aims to look at the problems associated with dynamic group communication compared to static group communication. It covers the basics of static group communication and multicasting as covered in the course material and then discusses the problems created by a dynamic group.
Introduction
Group communication is essential for distributed systems to allow processes to talk to each other. Messages are sent using various forms of multicast. Static group communication is where all processes in the group are initialised at the start and the group does not change and is well understood. Dynamic group communication, where group members change during computation, presents additional problems.
Group communication
Group communication is the infrastructure that allows a group of processes to communicate with each other [1]. It is best handled by middleware technologies e.g. ISIS, CORBA, JavaGroups and Totem [3]. Multicast communication is implemented where a message may have multiple recipients that are all members of a particular group of processes. This method of communicating is a basis for replication, improving fault tolerance and scalability of an application. IP multicast is an implementation of group communication based on top of IP. A class D address, which is a special kind of IP address is, is used to represent a group of machines. Multicast models can be classified in two different dimensions, atomicity and ordering. Atomicity is the extent of guarantee of deliverer offered by the multicast implementation. Ordering deals with guarantying the order in which messages are delivered, depending on what ordering policy is enforced e.g. FIFO, casual and total. Ordering of messages is especially important for replicated applications where replicas must stay consistent. IP multicast is unreliable so to improve on this a group communication layer is built on top of it. Basic multicast is any example of this. It involves each message containing a sequence number and sender id along with its data. Each process also has a sequence number representing the number of messages multicast to the group, and the highest sequence number of messages received from other group members, one value for each member in the group. This allows it to identify when it has received a message out of order. When a missing message is detected, the process sends a negative acknowledgement to the process that sent the message requesting a re-multicast. Processes that have received the message will ignore the re-multicast. Reliable multicast is a more complicated version of basic multicast with a similar algorithm. The main differences are that acknowledgements of multicast messages are sent out to all other processes during subsequent multicasts and each process keeps a log of all received messages. This adds redundancy, so that if a process receives a message out of order, but the process that the missing message is from has crashed, it can be resent from any other process that acknowledged receiving the message.
Dynamic Group Communication
The previous multicast algorithms are designed for closed or static groups, where the group membership does not change while the processes are running. Closed groups have limitations. Consider an example of a replicated server with 3 replicas. If one of these crashes, ideally another should be created. This requires the ability to dynamically add processes to the group. When group membership can change dynamically as processes join and leave the group, the problem becomes more complex [2]. Some examples of the differences are discussed below. In a dynamic group, the current group membership state is called a view. Each process in the group has this view. A process may request to add or remove another process from the view. The view is changed when this request is executed. In a static group, since processes should receive all messages, if a message is received out of order then the process requests the messages it expected to have received beforehand. In a dynamic group, processes that have joined after messages have begun to be sent need to be able receive a message without then requesting a previous message that was broadcast before it joined the group. Actual solutions for dynamic multicasting do not differ that much from solutions for static multicasting.
Conclusion
Dynamic group communication presents some interesting challenges not present for static group communication, however they can be overcome and the implementation does not differ by a lot from that of static multicasting solutions.
Reference
1 Group Communication: from practice to theory Andre Schiper Ecole Polytechnique Federale de Lausanne (EPFL) 2 Distrib. Comput. (2006) 18(5): 359–374 DOI 10.1007/s00446-005-0129-4 Andr´e Schiper Dynamic group communication Received: 23 August 2002 / Revised: 16 January 2005 / Accepted: 25 February 2005 / Published online: 31 December 2005 3 A Step Towards a New Generation of Group Communication Systems Sergio Mena, Andr´e Schiper, Pawe_l Wojciechowski Ecole Polytechnique F´ed´erale de Lausanne (EPFL) School of Computer and Communication Sciences Technical Report IC/2003/01 4 SE325 Course Notes