C. Beeri
D. E. Shasha
ABSTRACT
Concurrency control is the activity of synchronizing transactions that access shared data. A concurrency control algorithm is regarded as correct if it ensures that any interleaved execution of transactions is equivalent to a serial one. Such executions are called serializable. Serializability theory provides a method for modelling and analyzing the correctness of concurrency control algorithms [BSW, Pa].
The concept of nested transaction has recently received much attention [GR], [Mo]. In a nested transaction model, each transaction can invoke sub- transactions, which can invoke sub-subtransactions, and so on. The natural modelling concept is the tree log. The leaves of a tree log are atomic operations executed by the underlying system. Internal nodes are operations (as seen by their parents) implemented as transactions (as seen by their children). Nodes are related by a partial order <, where x<y means x executes before y [La].
- 1.Attar, R., P.A. Bernstein, and N. Goodman, "Site initialization, Recovery, and Back-up in a Distributed Database Systems," Proc. 6th Berkeley Workshop, Feb. 1982, pp. 185-202.Google Scholar
- 2.Bayer, R., H. Heller, and A. Reiser, "Parallelism and Recovery in Database Systems," ACM Trans. on Database Sys. 5:2 (June 1980), pp. 139-156. Google ScholarDigital Library
- 3.Bernstein, P.A., and N. Goodman, "Concurrency Control in Distributed Database Systems," ACM Computing Surveys 13, 2 (June 1981), pp. 185-221. Google ScholarDigital Library
- 4.Bernstein, P.A., and N. Goodman, "A Sophisticate's Introduction to Distributed Database Concurrency Control," Proc. 8th VLDE, Sept. 1982, pp. 62-76. Google ScholarDigital Library
- 5.Bernstein, P.A., and N. Goodman, "Multi-version Concurrency Control-Theory and Algorithms," Proc. of the ACM SIGACT-SIGOPS Conf. on Principles of Distributed Computation, August 1982, Ottawa.Google Scholar
- 6.Bernstein, P.A., N. Goodman, and M.Y. Lai, "Laying Phantoms to Rest (by Understanding the Interactions Between Schedulers and Translators in a Database System)," Proc. 1981 IEEE COMPSAC Conf., Oct. 1981.Google Scholar
- 7.Bernstein, P.A., D.W. Shipman, and W.S. Wong, "Formal Aspects of Serializability in Database Concurrency Control," IEEE Trans. on Software Engineering, SE-5, 3 (May 1979), 203-215.Google ScholarDigital Library
- 8.Chan, A., S. Fox, W.T. Lin, A. Nori, and D. Ries, "The Implementation of an Integrated Concurrency Control and Recovery Scheme," Proc. 1982 ACM SIGMOD Conf., ACM, N.Y. Google ScholarDigital Library
- 9.Dubourdieu, D.J., "Implementation of Distributed Transactions," Proc. 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, pp. 81-94.Google Scholar
- 10.Eswaran, K.P., Gray, J.N., Lorie, R.A., and Traiger, I.L., "The Notions of Consistency and Predicate Locks in a Database Systems," Communications of the ACM, vol. 19, No. 11, November 1976. Google ScholarDigital Library
- 11.Fischer, J.J., Griffeth, N.D., and N.A. Lynch, "Global States of a Distributed System," Proc. 1st IEEE Annual Symp. on Reliability in Distributed Software and Database Systems, 1981, pp. 31-38.Google Scholar
- 12.Gray, J., "The Transaction Concept: Virtues and Limitations," Proc. 7th International Conf. on Very Large Data Bases, Cannes, Sept. 1981, pp. 144-154.Google Scholar
- 13.Kwong, Y.S., and Wood, D., "A New Method for Concurrency in B-trees," IEEE Trans. Softw. Eng. SE-8, 3 (May 1982), pp. 211-222.Google ScholarDigital Library
- 14.Lamport, L., "Time, Clocks, and the Ordering of Events in a Distributed System," CACM, 21, 7 (July 1978), pp. 558-565. Google ScholarDigital Library
- 15.Lehman, P.L., and Bing Yao, S., "Efficient Locking for Concurrent Operations on B-Trees," ACM TODS 6:4 (Dec. 1981), pp. 650-670. Google ScholarDigital Library
- 16.Liskov, B., and W. Weihl, "Specification and Implementation of Resilient, Atomic Data Types," Manuscript, MIT Laboratory of Computer Sciences, 1982.Google Scholar
- 17.Lynch, N.A., "Concurrency Control for Resilient Nested Transactions," Proc. 2nd SIGACT-SIGMOD Conf. on Principles of Database Systems, Atlanta, March, 1983. Google ScholarDigital Library
- 18.Manna, Z., and A. Pnueli, book in preparation, 1983.Google Scholar
- 19.Moss, T.E.B., "Nested Transactions: An Approach to Reliable Distributed Computing," Ph.D. Thesis, MIT Laboratory for Computer Science, 1981.Google Scholar
- 20.Papadimitriou, C.H., "Serializability of Concurrent Updates," J. ACM 26:4 (Oct. 1979), pp. 631-653. Google ScholarDigital Library
- 21.Papadimitriou, C.H., and P.C. Kanellakis, "On Concurrency Control by Multiple Versions," Proc. 1st ACM SIGACT-SIGMOD Conf. on Principles of Database Systems, March 1982. Google ScholarDigital Library
- 22.Rosenkrantz, D.J., R.E. Stearns, and P.M. Lewis, "System Level Concurrency Control for Distributed Database Systems," ACM TODS 3:2 (June 1978), pp. 178-198. Google ScholarDigital Library
- 23.Reed, D., "Naming and Synchronization in a Decentralized Computer System," Tech. Rep. MIT/LCS/TR-205, MIT, Dept. of Elec. Eng. and Computer Science, Sept. 1978. Google ScholarDigital Library
- 24.Silberschatz, A., and Kedem, Z., "Consistency in Hierarchical Database Systems," J. ACM 27:1 (Jan. 1980), pp. 72-80. Google ScholarDigital Library
- 25.Schwartz, P., and Spector, A., "Synchronizing Shared Abstract Types," Tech. Rep. CMU-CS-82-128, CMU Dept. of Computer Science, Sept. 1982.Google Scholar
- 26.Stearns, R.E., P.M. Lewis II, and D.J. Rosenkrantz, "Concurrency Controls for Data-base Systems," Proc. 17th Symp. on Foundations of Computer Science, IEEE, N.Y., 1976, pp. 19-32.Google Scholar
- 27.Stearns, R.E., and D.J. Rosenkrantz, "Distributed Database Concurrency Controls Using Before-Values," Proc. 1981 ACM-SIGMOD Conf., ACM, N.Y., pp. 74-83. Google ScholarDigital Library
Index Terms
- A concurrency control theory for nested transactions (Preliminary Report)
Recommendations
Safe open-nested transactions through ownership
PPoPP '09Researchers in transactional memory (TM) have proposed open nesting as a methodology for increasing the concurrency of transactional programs. The idea is to ignore ``low-level'' memory operations of an open-nested transaction when detecting conflicts ...
Safe open-nested transactions through ownership
PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programmingResearchers in transactional memory (TM) have proposed open nesting as a methodology for increasing the concurrency of transactional programs. The idea is to ignore ``low-level'' memory operations of an open-nested transaction when detecting conflicts ...
Comments