Implementing Atomic Actions on Decentralized Data DAVID P. REED Massachusetts Institute of Technology Synchronization of accesses to shared data and recovering the state of such data in the case of failures are really two aspects of the same problem--implementing atomic actions on a related set of data items. In this paper a mechanism that solves both problems simultaneously in a way that is compatible with requirements of decentralized systems is described. In particular, the correct construction and execution of a new atomic action can be accomplished without knowledge of all other atomic actions in the system that might execute concurrently. Further, the mechanisms degrade gracefully if parts of the system fail: only those atomic actions that require resources in failed parts of the system are prevented from executing, and there is no single coordinator that can fail and bring down the whole system. Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems--distributed databases; D.4.3 [Operating Systems]: File Systems Management--distrib. uted file systems; H.2.2 [Database Management]: Physical Design--deadlock avoidance, recovery and restart; H.2.4 [Database Management]: Systems--distributed systems, transaction processing;, H.2.7 [Database Management]: Database Administration--logging and recovery General Terms: Algorithms, Reliability Additional Key Words and Phrases: time-domain addressing, two-phase commit, stable storage, nested atomic actions 1. INTRODUCTION The research reported here was begun with the intention of discovering methods for combining programmed actions on data at multiple decentralized computers into coherent actions forming a part of a distributed application program. The primary concerns were that it be easy to coordinate such combined actions with other concurrent actions accessing the same data, and that it be easy to handle failures in any part of the combined action. This research was supported in part by the Defense Advanced Research Projects Agency of the Department of Defense and monitored by the Office of Naval Research under contract no. N00014- 75-C-0661. Author's address: Laboratory for Computer Science, Massachussetts Institute of Technology, Cam- bridge, MA 02139. This paper was originally accepted for publication in Communications of the ACM. The CACM department editor responsible for the paper was Anita K. Jones. The author kindly agreed to publish the paper in ACM Transactions on Computer Systems. 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 specific permission. © 1983 ACM 0734-2071/83/0200-0003 $00.75 ACM Transactions on Computer Systems, Vol. 1, No. 1, February 1983, Pages 3-23.4 David P. Reed In the course of the research it became clear that coordinating access to data and recovery from failures were complementary mechanisms aimed at achieving the same goal: providing data and program modules whose behavior is easily specified without consideration for the details of the choice of data representation or the sequence of primitive steps executed that achieve the behavior. This goal is the familiar "information-hiding principle" elucidated by Parnas [17]. Atomic actions make the construction of such modules straightforward: by im- plementing operations of a module as atomic actions, concurrency and failure can be ignored. We describe a new method for synchronization and failure recovery that can be easily implemented in a decentralized system. We concentrate here particularly on the application of this method to the implementation of atomic actions. More general applications are described in the author's doctoral dissertation [19]. In the discussion that follows, we first define atomic actions and discuss the problems of implementing atomic actions in a decentralized system. We then describe a way of thinking about objects as sequences of unchangeable versions, object histories, that reflect the sequence of changes made to the object over time. Updating an object is thought of as creating a new version, while reading an object is thought of as selecting the proper version and obtaining its value. As part of this discussion, we describe two complementary techniques for coordinat- ing the versions of multiple objects--the possibility, which is a group of tentative versions created by updates that can be "simultaneously" added to the object histories, and pseudotime, which is a timelike ordering of events used to select the versions of objects that are read and created by a particular program. An example illustrating how the techniques work then follows. Finally, we compare these methods with traditional synchronization and recovery mechanisms. 2. ATOMIC ACTIONS We define an atomic action as a program-specified computation that, although composed of primitive computational steps executed at different times and in different places, cannot be decomposed from the point of view of computations outside the atomic action. During the execution of atomic actions, intermediate states of data objects that arise will never be observed by computations outside the atomic action. During the execution of an atomic action, objects whose values are read by steps of the atomic action can be modified only by other steps belonging to the atomic action during the execution of the atomic action. Concurrency and failure both threaten to decompose atomic actions. Two concurrent programs accessing a shared variable can interact in such a way that intermediate states of data within one program are observed by the other. If one program modifies the variable while the other is executing, the behavior of the first can be affected. Similarly, a program that halts because of a failure will leave intermediate states of data objects exposed. To say that a program specifies an atomic action means that the program must be atomic even in the face of concurrent execution and failures. We refine our definition by the following two requirements on the set of