Synchronization and recovery of actions

ABSTRACT

We introduce an approach to robust computation in distributed systems. This approach is the foundation for reliability in the Clouds decentralized operating system. It is based on atomic actions operating on instances of abstract data types (objects). We present an event-based model of computation in which scheduling of responses to operation invocations is controlled by objects. We discuss an integrated strategy for synchronization and recovery which uses relationships between the abstract states of objects to track dependencies between actions. Serializability is defined in terms of the semantics of operations. This permits high concurrency to be obtained in non-serializable implementations without deviation from serializable abstract behavior. We define a class of schedulers that allows objects to make autonomous scheduling decisions. We present the use of non-serializable operation semantics. Finally, we discuss implementation of the model, including action synchronization, object operation ordering using action-based counting semaphores, and action recovery.

REFERENCES

• 1: Three Rivers Computer Corp., Perq System Software Reference Manual, Pittsburgh, Pa., May 1982.
• 2: Allchin, J.E. and M.S. McKendry, "Object-based Synchronization and Recovery," Georgia Institute of Technology GIT-ICS-82/18, September 1982.
• 3: Allchin, J.E. and M.S. McKendry, Facilities for Supporting Atomicity in Operating Systems," Georgia Institute of Technology GIT-ICS-83/1, January 1983.
• 4: Allchin, J.E. and M.S. McKendry, "Support for Actions and Objects in Clouds: Status Report," Georgia Institute of Technology GIT-ICS-83/11, May 1983.
• 5: James Edward Allchin, An architecture for reliable decentralized systems, 1983
• 6: Bernstein, P., D. Shipman, and W. Wong, "Formal Aspects of Serializability in Database Concurrency Control," IEEE Transactions on Software Engineering, Vol. SE-5, No. 3, May 1979, pp. 203-215.
• 7: Bernstein P., N. Goodman, and M. Lai, "Two Part Proof Schema For Database Concurrency Control," Proceedings of the 5th Berkeley Workshop on Distributed Data Management and Computer Networks, February 1981, pp. 71-84.
• 8: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 9: Best, E., and B. Randell, "A Formal Model of Atomicity in Asynchronous Systems," Acta Informatica 16, 1981, 93-124.
• 10: Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
• 11: Charles T. Davies, Jr., Recovery semantics for a DB/DC system, Proceedings of the annual conference, p.136-141, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805694]
• 12: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 13: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 14: Jensen, E.D., "The Archons Project: An Overview," Proceedings International Symposium on Synchronization, Control, and Communication in Distributed Systems, Academic Press, 1983.
• 15: Henry F. Korth, Locking Primitives in a Database System, Journal of the ACM (JACM), v.30 n.1, p.55-79, Jan. 1983 [doi>10.1145/322358.322363]
• 16: H. T. Kung , C. H. Papadimitriou, An optimality theory of concurrency control for databases, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582114]
• 17: Barbara Liskov , Robert Scheifler, Guardians and actions: linguistic support for robust, distributed programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.7-19, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582155]
• 18: McKendry, M.S., J.E. Allchin, and W.C. Thibault, "Architecture for a Global Operating System," IEEE INFOCOM 83, April 1983.
• 19: C. Mohan , D. Fussell , A. Silberschatz, Compatibility and commutativity in non-two-phase locking protocols, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588157]
• 20: J. E.B. Moss, Nested transactions: an approach to reliable distributed computing, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 21: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 22: B. Randell , P. Lee , P. C. Treleaven, Reliability Issues in Computing System Design, ACM Computing Surveys (CSUR), v.10 n.2, p.123-165, June 1978 [doi>10.1145/356725.356729]
• 23: Richard F. Rashid , George G. Robertson, Accent: A communication oriented network operating system kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.64-75, December 14-16, 1981, Pacific Grove, California, United States
• 24: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 25: Lui Sha , E. Douglas Jensen , Richard F. Rashid , J. Duane Northcutt, Distributed co-operating processes and transactions, Proceedings of the symposium on Communications Architectures & Protocols, March 08-09, 1983, Austin, Texas
• 26: Schwarz, P. and A. Spector, "Synchronizing Shared Abstract Types," Technical Report CMU-82-128, Department of Computer Science, CMU, September 1982.
• 27: Weihl, W. and B. Liskov, "Specification and Implementation of Resilient, Atomic Data Types," Computation Structures Group Memo 223, MIT, December 1982.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

General Terms:
Management, Reliability