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 T h e research r e p o r t e d here was begun with the intention of discovering m e t h o d s for c o m b i n i n g p r o g r a m m e d actions on data at multiple decentralized c o m p u t e r s into c o h e r e n t actions forming a part of a distributed application program T h e p r i m a r y concerns were t h a t it be easy to coordinate such c o m b i n e d actions with o t h e r c o n c u r r e n t a c t i o n s a c c e s s i n g t h e s a m e d a t a a n d t h a t it b e e a s y t o h a n d l e f a i l u r e s in a n y p a r t o f t h e c o m b i n e d a c t i o n 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 N0001475 C 0661 Author s address Laboratory for Computer Science Massachussetts Institute of Technology Cambridge 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 implementing 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 coordinating 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 o u r definition by the following two requirements on the set of computational steps in an atomic action Ap specified by program P ACM Transactions on Computer Systems Vol 1 No 1 February 1983