Abstract
Concurrency control algorithms have traditionally been based on locking and timestamp ordering mechanisms. Recently optimistic schemes have been proposed. In this paper a distributed, multi-version, optimistic concurrency control scheme is described which is particularly advantageous in a query-dominant environment. The drawbacks of the original optimistic concurrency control scheme, namely that inconsistent views may be seen by transactions (potentially causing unpredictable behavior) and that read-only transactions must be validated and may be rolled back, have been eliminated in the proposed algorithm. Read-only transactions execute in a completely asynchronous fashion and are therefore processed with very little overhead. Furthermore, the probability that read-write transactions are rolled back has been reduced by generalizing the validation algorithm. The effects of global transactions on local transaction processing are minimized. The algorithm is also free from dedlock and cascading rollback problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agrawal R, Carey MJ, Livny M (1985) Models for studying concurrency control performance: Alternatives and implications. Proc ACM-SIGMOD, Texas (May 1985) pp 108–121
Agrawal R, Dewitt DJ (1985) Integrated concurrency control and recovery mechanisms: Design and performance evaluation. ACM Trans Database Syst 4: 529–564
Bernstein PA, Goodman N (1981) Concurrency control in distributed database systems. Comput Surv 2: 185–221
Bragger RP, Reimer M (1983) Predicative Scheduling: Integration of Locking and Optimistic Methods. Tech Rep Eidgenössische Technische Hochschule (ETH), Zürich (July 1983)
Ceri S, Owicki S (1982) On the use of optimistic methods for concurrency control in distributed databases. Proc 6th Berkeley Workshop in distributed data management and computer networks (Feb 1982) pp 117–129
Chan A, Fox S, Lin WK, Nori A, Ries DR (1982) The implementation of an integrated concurrency control and recovery scheme. Proc ACM-SIGMOD, Florida (July 1982) pp 184–191
Eswaran KP, Gray JN, Lorie RA, Traiger IL (1976) The notion of consistency and predicate locks in database system. Commun ACM 11: 624–633
Gray JN (1978) Notes on data base operating systems. In: Bayer R, Graham RM, Seegmuller G (eds) Operating systems. An advanced course. Lect Notes Comput Sci, vol 60. Springer, Berlin Heidelberg New York pp 393–481
Kung HT, Robinson JT (1981) On optimistic methods for concurrency. ACM Trans Database Syst 2: 213–226
Lai MY, Wilkinson WK (1984) Distributed transaction management in JASMIN. Proc 10th Int Conf on very large data bases, Singapore (August 1984) pp 466–470
Lamport L (1978) Time, clocks, and the ordering of events in a distributed system. Commun ACM 7:558–565
Lampson BW, Sturgis HE (1979) Crash recovery in a distributed data storage system. Computer Science Laboratory, Xerox Palo Alto Research Center
Lausen G (1982) Concurrency control in database systems: A step towards the integration of optimistic methods and locking. Proc ACM Annual Conf, Dallas, TX (Oct 1982) pp 64–68
Lehman PL, Yao SB (1981) Efficient locking for concurrent operations on B-trees. ACM Trans Database Syst 4:650–670
Mohan C, Lindsay B (1985) Efficient commit protocols for the tree of processes model of distributed transactions. ACM Operating Syst Review 2:40–52
Reed DP (1978) Naming and Synchronization in a Decentralized Computer System. Tech Rep MIT/LCS/TR-205, MIT (September 1978)
Schlageter G (1981) Optimistic Methods for Concurrency Control in Distributed Database Systems. Proc 7th Int Conf on very large data bases, Cannes (September 1981) pp 125–130
Author information
Authors and Affiliations
Additional information
Divyakant Agrawal is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Burroughs Limited, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include design of algorithms for concurrent systems, optimistic protocols and distributed systems.
Arthur Bernstein is a Professor of Computer Science at the State University of New York at Stony Brook. His research is concerned with the design and verification of algorithms involving asynchronous activity and with languages for expressing such algorithms.
Pankaj Gupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received M.S. degree in Electrical Engineering from SUNY at Stony Brook in 1982 and M.S. degree in Computer Science from SUNY at Stony Brook in 1985. His research interests include distributed systems, concurrency control, and databases.
Soumitra Sengupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Consultancy Services, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include distributed algorithms, logic databases and concurrency control.
This work was supported by the National Science Foundation under grant, DCR-8502161 and the Air Force Office of Scientific Research under grant AFOSR 810197
Rights and permissions
About this article
Cite this article
Agrawal, D., Bernstein, A.J., Gupta, P. et al. Distributed optimistic concurrency control with reduced rollback. Distrib Comput 2, 45–59 (1987). https://doi.org/10.1007/BF01786254
Issue Date:
DOI: https://doi.org/10.1007/BF01786254