Transactions: a construct for reliable distributed computing

ABSTRACT

Transactions have proven to be a useful tool for constructing reliable database systems and are likely to be useful in many types of distributed systems. To exploit transactions in a general purpose distributed system, each node can execute a transaction kernel that provides services necessary to support transactions at higher system levels. The transaction model that the kernel supports must permit arbitrary operations on the wide collection of data types used by programmers. New techniques must be developed for specifying the synchronization and recovery properties of abstract types that are used in transactions. Existing mechanisms for synchronization, recovery, deadlock management and communication are often inadequate to implement these types efficiently, and they must be adapted or replaced.

REFERENCES

• 1: James E. Allchin and Martin S. McKendry. Object-Based Synchronization and Recovery, 1982. School of Information and Computer Science, Georgia Institute of Technology, submitted for publication.
• 2: P. A. Bernstein, N. Goodman, and M. Y. Lai. Two Part Proof Schema for Database Concurrency Control. In Proc. Fifth Berkeley Wkshp. on Dist. Data Mgmt. and Computer Networks, pages 71--84. February, 1981.
• 3: Dean Daniels. Query Compilation in a Distributed Database System. Master's thesis, MIT, March, 1982.
• 4: Decsystem10 Assembly Language Handbook 2 edition, Digital Equipment Corporation, Maynard, MA, 1972.
• 5: 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]
• 6: H. Garcia-Molina. Using Semantic Knowledge for Transaction Processing in a Distributed Database. Technical Report 285, Department of Electrical Engineering and Computer Science, Princeton, June, 1982.
• 7: David K. Gifford. Violet, an Experimental Decentralized System. In Proceedings I.R.I.A. Workshop on Integrated Office Systems. Versailles, France, November, 1979. Also available as Xerox Palo Alto Research Center Report CSL-79-12.
• 8: J. N. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base. IBM Research Report RJ1654, IBM Research Laboratory, San Jose, Ca., September, 1975.
• 9: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 10: Jim Gray. A Transaction Model. IBM Research Report RJ2895, IBM Research Laboratory, San Jose, Ca., August, 1980.
• 11: Jim Gray. The Transaction Concept: Virtues and Limitations. In Proc. of Very Large Database Conference, pages 144--154. September, 1981.
• 12: Jim Gray, Pete Homan, Ron Obermarck, Hank Korth. A Straw Man Analysis of Probability of Waiting and Deadlock. IBM Research Report RJ3066, IBM Research Laboratory, San Jose, Ca., February, 1981.
• 13: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 14: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 15: David M. Jacobson. Transactions on Objects of Arbitrary Type. Technical Report 82--05-02, University of Washington, May, 1982.
• 16: Henry F. Korth. A Deadlock-Free Variable Granularity Locking Protocol. In Proc. Fifth Berkely Wkshp. on Dist. Data Mgmt. and Computer Networks. February, 1981.
• 17: 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]
• 18: 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]
• 19: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 20: Wen-Te K. Lin, Jerry Nolte. Performance of Two Phase Locking. In Proceedings 7th Berkeley Conference on Distributed Data Management and Computer Networks. February, 1982.
• 21: Bruce G. Lindsay, et al. Notes on Distributed Databases. IBM Research Report RJ2571, IBM Research Laboratory, San Jose, Ca., July, 1979.
• 22: 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]
• 23: Barbara Liskov. On Linguistic Support for Distributed Programs. IEEE Trans. on Software Engineering SE-8(3):203--210, May, 1982.
• 24: D. B. Lomet, Process structuring, synchronization, and recovery using atomic actions, ACM SIGPLAN Notices, v.12 n.3, p.128-137, March 1977
• 25: Raymond A. Lorie, Physical integrity in a large segmented database, ACM Transactions on Database Systems (TODS), v.2 n.1, p.91-104, March 1977 [doi>10.1145/320521.320540]
• 26: J. Eliot B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, MIT, April, 1981.
• 27: David P. Reed. Naming and Synchronization in a Decentralized Computer System. PhD thesis, MIT, September, 1978.
• 28: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]
• 29: Lawrence A. Rowe, Kenneth P. Birman. Network Support for a Distributed Data Base System. In Proceedings 4th Berkeley Conference on Distributed Data Management and Computer Networks, pages 337--352. August, 1979.
• 30: J. H. Saltzer, D. P. Reed, D. D. Clark. End-To-End Arguments in System Design. In Proceedings 2nd International Conference on Operating Systems, pages 519--512. Paris, France, April, 1981.
• 31: Peter M. Schwarz, Alfred Z. Spector. Synchronizing Shared Abstract Types. Carnegie-Mellon Report CMU-CS-82--128, Carnegie-Mellon University, Pittsburgh, PA, September, 1982.
• 32: 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
• 33: Alfred Z. Spector, Performing remote operations efficiently on a local computer network, Communications of the ACM, v.25 n.4, p.246-260, April 1982 [doi>10.1145/358468.358478]
• 34: William E. Weihl. Atomic Actions and Data Abstractions. 1981. MIT Laboratory for Computer Science.