We describe applications of a virtually synchronous environment for distributed programming, which underlies a collection of distributed programming tools in the 1SIS2 system. A virtually synchronous environment allows processes to be structured into process groups, and makes events like broadcasts to the group as an entity, group membership changes, and even migration of an activity from one place to another appear to occur instantaneously --in other words, synchronously. A major advantage to this approach is that many aspects of a distributed application can be treated independently without compromising correctness. Moreover, user code that is designed as if the system were synchronous can often be executed concurrently. We argue that this approach to building distributed and fault-tolerant software is more straightforward, more flexible, and more likely to yield correct solutions than alternative approaches. Consider the design of a distributed system for factory automation, say for VLSI chip fabrication. Such a system would need to group control 'processes into services responsible for different aspects of the fabrication procedure. One service might accept batches of chips needing photographic emulsions, another oversee transport of chips from station to station, etc. Within a service, algorithms would be needed for scheduling work, replicating data, coordiThis work was supported by the Defense Advanced Research Projects Agency (DoD) under ARPA order 5378, Contracts MDA903-85-C-0124 and N00140-87-C-8904, and by the National Science Foundation under grant DCR-8412582. The views, opinions and findings contained in this report are those of the authors and should not be construed as an official Department of Defense position, policy, or decision. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specfic permission. nating actions at physmally separate locations, load balancing, and dynamically reconfiguring the system after a component goes off line or comes back on line. The premise of the ISIS project and this paper is that the existing software development methodology is inadequate to address this class of applications. Here, we put forward a new approach that permits applications to be decomposed into orthogonal components that can be treated separately and in a surprisingly "non-distributed" fashion. Our research seeks to provide a toolkit for distributed programming to assist in solving those sub-problems that arise most commonly in distributed systems. Each tool consists of a set of subroutines callable from application software, in some cases augmented by a distributed program that maintains persistent state information. Users develop software by interconnecting nondistributed programs using the tools. ISIS2 provides tools for initiating asynchronous actions, updating replicated data without blocking, obtaining mutual exclusion using fault-tolerant replicated semaphores, and many others. A distributed program that uses replicated data would consist of a set of conventional programs, each of which performs subroutine calls to the appropriate tool to access their shared state. The essential issue in designing the toolkit is to ensure that the tools have orthogonal functionality, since it is this aspect that permits the programmer to break up an application into components that can be solved independently and extended gradually into a complete system. A second issue relates to concurrency. In order to make full use of the potential for concurrency available in a distributed system, processes must be able to make local decisions whenever possible, since a process that must interact with others before making a decision would be delayed until they respond. To address these issues we have ©1987 [Peterson] (who develop mechanisms for supporting asynchronous executions that exhibit properties similar to virtual synchrony). Since virtual synchrony combines a notion of atomicity with an ordering restriction, it is also related to transactional serializability, although nothing analogous to the "transaction" exists in a virtually synchronous setting. What we have done in the 1SIS 2 project is essentially to unify these concepts, weakening some aspects that proved to be overly limiting, and optimizing behavior in the common situations that arise when asynchronous computation is desired and failures can occur. The result is a system capable of satisfying even demanding practitioners that is at the same time formally rigorous. This paper begins by exploring the concept of virtual synchrony and the ways that it is reflected in the interfaces provided by the 1SIS 2 toolkit. We illustrate these mechanisms by examining the internal stepwise development of an ISIS 2 application and of a typical toolkit routine. We then examine performance issues. Virtual synchrony In this work, we assume that a distributed system consists of processes with disjoint address spaces communicating over a conventional LAN using message passing. Processes are assumed to execute on computing sites. Individual processes and entire sites can crash; the former type of crash is assumed detectable by some monitoring mechanism at the site of the process, while the latter can only be detected by another site by means of a timeout. It is assumed that failing processes send no incorrect messages. Our system tolerates message loss, but not partitioning failures (wherein links that interconnect groups of sites fail). Partitioning could cause parts of our system to hang until communication is restored. We now enumerate some of the specific subproblems we wish to solve in this setting; each of these corresponds to a separate tool within 1SIS 2. often desirable to structure a system into "groups" of (possibly non-identical) processes --such a group might implement a high level abstraction like the emulsion depositing service, or a low level one, like a replicated data item. Ideally, such a mechanism should enable each process to belong to multiple process groups, provide flexible mechanisms for joining and leaving groups, and be inexpensive. Also needed is a facility for communicating with the members of a group while membership is changing. Deciding how to respond to a request. When a group of processes receives a request, a strategy must be devised for executing it. The process group mechanism should enable a process to respond to a request using only local information (without running any agreement protocol among the group members), if it is practical to do so. As much as possible, designers will need to exploit the concurrency available in a distributed system, for example by arranging for several processes to take actions at the same time, or to continue executing asynchronously after sending a message to inform other processes of some event (without waiting for that message to be delivered). Synchronization. On the flip side of the coin, processes executing concurrently will need locking 124 and mutual exclusion mechanisms to avoid interference between concurrent activities. These mechanisms must also deal with the failure of a process h01d-ing a lock or semaphore, and with deadlock detection. R e p l i c a t e d data. Many applications require efficient mechanisms for replicating data, at the level of individual data structures, and among cooperating but not necessarily identical processes. Detecting and reacting to a failure. A mechanism is required for detecting failures and informing any interested parties of a failure. For example, when the members of a group are cooperating to respond to a request from a caller, operational members should be informed if a member fails, and the caller should be informed if all members fail. One would also like the assurance that a message from a failed process will never be delayed so long as to arrive after the failure has already been observed. D y n a m i c reconfiguration. After a failure, recovery, or in response to certain types of requests or changes in system load, it may be desirable to adjust the system configuration. To be practical, this must impact as little as possible on new and ongoing activities. If processes need to recover their state after a failure, a mechanism is needed for creating periodic checkpoints or logs that can be replayed on recovery. It should be possible to design software capable of recovering after failures. After a total failure, where all the processes that make up an application crash simultaneously, the need is to restart the whole application gracefully using its stable state. The second and more common problem is to recover from a partial failure, when a failed process is attempting to recover while the remainder of the system is still operational. Mechanisms are needed for reintegrating such a process into the system, and perhaps for transferring some part of the current system state to it. Transactions. Applications that manage shared complex disk-based data structures or distributed ones will sometimes need ways to access and update them as a transaction. Even though the focus of ISIS 2 is on non-transactional software, such applications will need to be supported, and they should be able to make use of the remainder of ISIS 2 as well. To the maximum extent that is practical, the IS1S2 system must protect itself and its clients against actions by erroneous clients. Consistency. Pervading the above discussion is an implicit notion of consistency. Despite the uncertainty of the system state introduced by concurrency and failures, the designer needs to know that there is some sense in which the operational processes in the system will satisfy a global correctness constraint. As far as possible, given locally correct algorithms one would like to know that a globally correct system will result from interconnecting them. In particular, concurrency should not introduce subtle correctness problems, even when processes are sometimes out of synch with other processes they need to interact with. What makes problems hard to tackle in a conventional environment is the asynchronous propagation of information among processes. In the absence of shared memory, the only way a process can learn of the behavior of other processes is through messages it receives. Since message transmission times vary from process to process, and change with the load on the system, messages relating to a single event may arrive at different processes at different times, and in different orders relative to other messages. Further, the failure of a process can only be detected when a timeout occurs while waiting for a message from it, and hence cannot be distinguished from a transient communication failure or an overload. All this makes it difficult for a set of processes to maintain a consistent view of one another's status, or for them to coordinate their actions efficiently. We believe that the current distributed programming methodologies are inadequate in light of these concerns. Most distributed systems are based on remote procedure calls (RPC) with timeout for failure detection [Birrell]: a mechanism that provides almost no support for any of the issues cited above. The current trend is to turn to nested transactions [Moss] or atomic actions for purposes of fault-tolerance, but these provide only a limited solution. Transactions facilitate the management of stable storage, but they offer no help in integrating a recovered state with the current state of the rest of the system. In large systems, transactional concurrency control can be overly restrictive: many of the behaviors listed above are inherently nonserializable. Further, long computations tend to lock shared data structures for extended periods, delaying other computations. We claim that transactions are the appropriate mechanism in situa-125 tions that involve short-lived access to shared data stored on a disk. Alternatives are needed in other situations. One way out of the problems enumerated in Sec. 2.2 would be to base the system on atomic multicast protocols.1 A multicast is atomic if all of its operational destinations receive the message unless the sender fails, in which case either all receive it or none does so. Moreover, all recipients see the same message delivery ordering. We need to extend this definition of atomicity to cover the case of a multicast whose destinations include process groups with memberships that may be changing. Such a multicast should logically be delivered to the group membership that applied when it was invoked, but this may not be the one that is current at the time of delivery. We will consequently require that the delivery of an atomic multicast is always completed before a group that forms part of its destinations is allowed to take on a new member. We point out that many existing atomic multicast protocols assume static sets of destinations that are known when the protocol is initiated [Chang] [Cristian] [Schneider-b]. We will use the term synchronous to a describe an environment in which multicasts are atomic and events such as message deliveries, process and site failures, recoveries, and other events described below, occur in the same order everywhere. In a synchronous environment, mechanisms solving all the problems cited above can be implemented without much difficulty. Processes can easily maintain a consistent view of one another, as each process is always in the same point in its computation as any other. Synchronization, when needed, is simple for the same reason. Process failures can be handled consistently because all operational processes learn of a failure simultaneously, in the same computational step. Unfortunately, this is prohibitively expensive. The problem is that it requires all message deliveries to be ordered relative to one another, regardless of whether the application needs this to maintain consistency. The protocols needed to achieve such a strong ordering are invariably costly, both in terms of 1This is a multi'cast to a set of processes, not a broadcast to all the machines connected to a local network with a hardware broadcast capability. Such hardware might, however, be exploited to optimize the implementation of the multicast protocol [Babaoglu]. the number of messages sent and in terms of the time spent waiting for them to terminate. This leads us to the concept of virtual synchrony. The basic idea is to preserve the illusion that events are occurring instantaneously, but to use different communication primitives that enforce weaker delivery orderings in situations where the application or tool is insensitive to the delivery ordering. For example, one could imagine a multicast primitive that delivers messages in the order that the sending process sent them, but is completely unordered relative to multicasts from other origins. A process with private access to a replicated FIFO queue could use this primitive to update it, since updates would be processed in the same order at all copies. On the other hand, if more than one process can perform operations on the queue, this primitive would be inadequate, because updates from different processes might be processed out of order. The advantage of using this primitive in the former case is that it is likely to have a cheaper implementation than a full atomic multicast, and yet gives the degree of synchrony needed for that application. A virtually synchronous execution is thus characterized by the following property: It will appear to any observer --any process using the system --that all processes observed the same events in the same order. This applies not just to message delivery events, but also to failures, recoveries, group membership changes, and other events described below. As we will see in the next section, this enables one to make apriori assumptions about the actions other processes will take, and simplifies algorithmic design. Recall that the actual sequence of events will sometimes differ from process to process in situations where the resulting actions are the same (or semantically equivalent) to those that would have been taken had the event sequences actually been identical. We will exploit this to increase concurrency. The above discussion is so focused on atomic multicasting that one might conclude that this is all 1SIS 2 provides. In fact, we view atomic multicasts as just one of a family of tools that all provide virtually synchronous behavior. For example, there is a tool that supports bulk transfers of information between processes in a way that looks instantaneous. Another 126 tool makes updates to replicated data appear to be instantaneous. The actual implementations of the tools, moreover, are highly concurrent and asynchronous. The main point is that they can be used as if they were synchronous. Furthermore, the tools meet our goal of orthogonality. After developing an application using the replication tool, one can extend it using the state transfer tool: these two kinds of "instantaneous" events are guaranteed not to conflict. These and other tools are described in the next section. This section reviews some of the tools supported by 1S1S 2, describing both the role of each tool and the sense in which its behavior is virtually synchronous. Our aim in chosing this set of tools was to enable one to develop applications using a small set of tools, and then to add functionality by invoking additional tools, making only minor changes to the existing code. We expect the tools to grow into an extensive collection covering most of the problems that arise commonly in distributed systems. We begin our discussion with the lowest level of the system, which provides communication primitives, and then work up to higher level tools, many of which use these primitives. Except in Section 3.11, we restrict ourselves to tools that are fully operational (as of August, 1987) . The three primitives described below, ABCAST, CBCAST and GBCAST have been described in [Birman-a]. The implementation is faithful to the one in that paper and is not discussed here. Readers familiar with the primitives may wish to skip to Section 3.2. ABCAST primitive. A commonly occurring situation involves a number of concurrently executing processes that communicate with a shared distributed resource, whose internal state is sensitive to the order in which requests arrive at different components of the resource. For example, concurrent operations on a shared replicated FIFO queue must be received and processed at all copies in the same order. This ordering requirement corresponds to the primitive we call ABCAST, which delivers messages atomically and in the same order everywhere. If all requests for queue operations are transmitted using this primitive, the enqueuing operations would look synchronous relative to other such operations on the same queue. CBCAST primitive. The correctness of a replicated FIFO queue depends on preserving the order of all operations performed on it. Consider, instead, a service that maintains a set of replicated variables on behalf of several clients. Each client has exclusive access to its variables. Although the service is likely to receive requests concurrently from many clients, it is only necessary to preserve the order of requests originating from the same client. Clearly, a multicast primitive weaker than ABCAST could be used in this case. On the other hand, because of remote procedure calls, a computation could span multiple processes, and hence messages sent by the same client could originate from several different processes. Short of ordering all multicasts, is there a way of characterizing the ordering requirement applicable in this case? Lamport observed that in a distributed system, the ordering of events is meaningful only when information could have flowed from one to the other through some chain of message transmissions, receptions and intervening local computations [Lamport-b]. It follows that we can define two multicast events to be potentially causally related if information about the first could have reached the point where the second was begun before it was initiated there. Notice that by this definition, two multicasts issued by a single computation are always potentially causally related. This leads us to the primitive called CBCAST, which guarantees that if any invocations of CBCAST are potentially causally related, the corresponding messages are delivered everywhere in the order of invocation. This is a conservative 2 approach to ensuring that any genuinely related operations will be seen in the correct order.
Coordination is achieved automatically through the use of a shared tuple space, for which two implementations were tested-a centralized one, and a decentralized one based on the concept of virtual synchrony REF .
Exploiting virtual synchrony in distributed systems
SOSP '87
Computer Science