GROUP COMMUNICATION IN AMOEBA AND ITS APPLICATIONS M Frans Kaashoek Andrew S Tanenbaum Kees Verstoep Dept of Math and Comp Sci Vrije Universiteit Amsterdam The Netherlands Email kaashoek lcs mit edu ast cs vu nl and versto cs vu nl ABSTRACT Unlike many other operating systems Amoeba is a distributed operating system that provides group communication i e one to many communication We will discuss design issues for group communication Amoeba s group system calls and the protocols to implement group communication To demonstrate that group communication is a useful abstraction we will describe a design and implementation of a fault tolerant directory service We discuss two versions of the directory service one with Non Volatile RAM NVRAM and one without NVRAM We will give performance figures for both implementations 1 Introduction Most current distributed operating systems provide only Remote Procedure Call RPC 6 The idea is to hide the message passing and make the communication look like an ordinary procedure call see Figure 1 The sender called the client calls a stub routine on its own machine that builds a message containing the name of the procedure to be called and all the parameters It then passes this message to the driver for transmission over the network When it arrives the remote driver gives it to a stub which unpacks the message and makes an ordinary procedure call to the server The reply from server to client follows the reverse path Client machine Client Stub Server machine Driver Network Driver Stub Figure 1 Remote procedure call from a client to a server Current affiliation Lab for Computer Science MIT Cambridge MA Server 2Although RPC is a very useful communication paradigm many applications need something more RPC is inherently point to point communication but what often is needed is 1 to n communication Consider for example a parallel application Typically in a parallel application a number of processes cooperate to compute a single result If one of the processes finds a partial result e g a better bound in a parallel branch and bound program it is often necessary that this partial result is communicated immediately to the other processes so that they do not waste cycles on computing something that is not interesting anymore given the new partial result What is needed here is a way to send a message from 1 process to n processes This abstraction is called group communication Now consider a second application a fault tolerant storage service A reliable storage service can be built by replicating data on multiple processors each with its own disk If a piece of data needs to be changed the service either has to send the new data to all processes or invalidate all other copies of the changed data If only point to point communication were available then the process would have to send n 1 reliable point to point messages In most systems this will cost at least 2 n 1 messages one packet for the actual message and one packet for the acknowledgement If the message sent by the server has to be fragmented into multiple network packets then the cost will be even higher This method is slow inefficient and wasteful of network bandwidth In addition to being expensive building distributed applications using only point to point communication is often difficult If for example two servers in the reliable storage service receive a request to update the same data they need a way to order the updates otherwise the data may become inconsistent The problem is illustrated in Figure 2 The copies of variable x become inconsistent because the messages from Server 1 and Server 2 are not ordered The problem of ordering is not restricted to point to point communication however Many network designers have realized that group communication is an important tool for building distributed applications broadcast communication is provided by many networks including LANs geosynchronous satellites and cellular radio systems 33 Several commonly used LANs such as Ethernet and some rings even provide multicast communication Using multicast communication messages can be sent exactly to the group of processes that are interested in receiving them Future networks like Gigabit LANs are also likely to implement broadcasting and or multicasting to support high performance applications such as multimedia 22 The protocol presented in this paper for group communication uses the hardware multicast capability of a network if one exists Otherwise it uses broadcast messages or point to point messages depending on the size of the group and the availability of broadcast communication Thus Amoeba makes the hardware support for group communication available to application programs The outline of the rest of the paper is as follows In Section 2 we will discuss design issues in group communication In Section 3 we will discuss the Amoeba group system calls Section 4 gives an overview of the protocols that are used to implement group communication in Amoeba In Section 5 we will describe the design and implementation of a distributed application using group communication a fault tolerant directory service In Section 6 we will give performance figures for two implementations of the directory service In Section 7 some conclusions will be drawn 3 Server1 X 2 Server2 X X 1 1 Server1 Server2 X 2 X 2 X X 3 Server1 Done X 3 3 Server2 X X 3 2 Done Figure 2 Inconsistency due to lack of message ordering 2 Design Issues in Group Communication Few existing operating systems provide application programs with support for group communication To understand the differences between these existing systems six design criteria are of interest addressing reliability ordering delivery semantics response semantics and group structure see Table 1 We will discuss each one in turn Issue Description Addressing Addressing method for a group e g list of members Reliability Reliable or unreliable communication Ordering Order among messages e g total ordering Delivery semantics How many processes must receive the message successfully Response semantics How to respond to a broadcast message Group structure Semantics of a group e g dynamic versus static Table 1 The main design issues for group communication Four methods of addressing messages to a group exist 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