Data-dependent concurrency control and recovery (Extended Abstract)

ABSTRACT

Maintaining the consistency of long-lived, on-line data is a difficult task, particularly in a distributed system. A variety of researchers have suggested atomicity as a fundamental organizational concept for such systems. In this paper we present a formal treatment of atomicity. Our treatment is novel in three respects: First, we treat serializability and recoverability together, facilitating the precise analysis of online implementations. Second, we explore how to analyze user specified semantic information to achieve greater concurrency. Third, we focus on local properties of components of a system, thus supporting modular design. We present three local properties, verify that they ensure atomicity, and show that they are optimal. Previously published protocols are suboptimal. We show that these differences are the result of fundamental limitations in the model used to analyze those protocols; these limitations are not shared by our model.

REFERENCES

• 1: Bernstein, P., Goodman, N., and Lai, M.Y. Two part proof schema for database concurrency control. In Proceedings of the Fifth Berkeley Workshop on Distributed Data Management and Computer Networks, pages 71-84. February, 1981.
• 2: Bernstein, P. A. and Goodman, N. Multiversion concurrency control—theory and algorithms. Technical Report, Harvard University Aiken Computation Laboratory, June, 1982.
• 3: 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]
• 4: Davies, C. T. Data processing spheres of control. IBM Systems Journal 17(2):179-198, 1978.
• 5: DuBourdieu, D.J. Implementation of distributed transactions. In Proceedings of the Sixth Berkeley Workshop on Distributed Data Management and Computer Networks, pages 81-94. 1982.
• 6: 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]
• 7: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 8: Kanellakis, P. and Papadimitriou, C. On concurrency control by multiple versions. In Proceedings of the 1982 ACM Symposium on Theory of Computing. 1982.
• 9: Henry Francis Korth, Locking protocols: general lock classes and deadlock freedom, 1981
• 10: Lamport, L. Towards a theory of correctness for multi-user data base systems. Technical Report CA-7610-0712, Massachusetts Computer Associates, October, 1976.
• 11: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 12: Lampson, B. W. and H. E. Sturgis. Crash recovery in a distributed data storage system. Submitted to CACM.
• 13: Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983 [doi>10.1145/2166.357215]
• 14: Barbara Liskov , Stephen Zilles, Programming with abstract data types, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.50-59, March 28-29, 1974, Santa Monica, California, United States
• 15: 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]
• 16: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 17: Schwarz, P., and Spector, A. Synchronizing shared abstract types. Technical Report CMU-CS-82-128, Carnegie-Mellon University, September, 1982.
• 18: Weihl, W. E. A method for the construction of modular, reliable, concurrent systems. PhD thesis, MIT, 1983. Forthcoming.
• 19: Weihl, W. E. Long read-only actions. Unpublished memo, 1982.
• 20: William Weihl , Barbara Liskov, Specification and implementation of resilient, atomic data types, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.53-64, June 27-29, 1983, San Francisco, California, United States

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

General Terms:
Theory