On Optimistic Methods for Concurrency Control.

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981)
  author    = {H. T. Kung and
               John T. Robinson},
  title     = {On Optimistic Methods for Concurrency Control},
  journal   = {ACM Trans. Database Syst.},
  volume    = {6},
  number    = {2},
  year      = {1981},
  pages     = {213-226},
  ee        = {, db/journals/tods/KungR81.html},
  bibsource = {DBLP,}


Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are presented. The methods used are "optimistic" in the sense that they rely mainly on transaction backup as a control mechanism, "hoping" that conflicts between transactions will not occur. Applications for which these methods should be more efficient than locking are discussed.

Copyright © 1981 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

  1. Jens Lechtenbörger, Gottfried Vossen: On Herbrand Semantics and Conflict Serializability of Read-Write Transactions. PODS 2000: 187-194
  2. Yukari Shirota, Atsushi Iizawa, Hiroko Mano, Takashi Yano: The ECHO Method: Concurrency Control Method for a Large-Scale Distributed Database. ICDE 1999: 174-183
  3. Shirish Hemant Phatak, B. R. Badrinath: Multiversion Reconciliation for Mobile Databases. ICDE 1999: 582-589
  4. Shalab Goel, Bharat K. Bhargava, Sanjay Kumar Madria: An Adaptable Constrained Locking Protocol for High Data Contention Environments. DASFAA 1999: 321-328
  5. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
  6. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  7. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control Algorithms for Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
  8. Suresh Kumar, Eng-Kee Kwang, Divyakant Agrawal: Caprera: An Activity Framework for Transaction Processing on Wide-Area Networks. VLDB 1997: 585-589
  9. George T. Heineman, Gail E. Kaiser: The CORD Appraoch to Extensible Concurrency Control. ICDE 1997: 562-571
  10. Ekaterina Pavlova, Igor Nekrestyanov: Concurrency Control Protocol for Nested Transactions in Real-Time Databases. ADBIS 1997: 23-28
  11. Sanjay Kumar Madria, Bharat K. Bhargava: System Defined Prewrites for Increasing Concurrency in Databases. ADBIS 1997: 18-22
  12. C. K. Kim, Janusz R. Getta: Concurrency Control in Active Database Systems with Prioritised Rules. ADBIS 1997: 29-34
  13. Malcolm P. Atkinson, Ronald Morrison: Orthogonally Persistent Object Systems. VLDB J. 4(3): 319-401(1995)
  14. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers, Lijing Lin: Ordered Shared Locks for Real-Time Databases. VLDB J. 4(1): 87-126(1995)
  15. Alexander Thomasian: Checkpointing for Optimistic Concurrency Control Methods. IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
  16. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  17. Henry F. Korth: The Double Life of the Transaction Abstraction: Fundamental Principle and Evolving System Concept. VLDB 1995: 2-6
  18. Azer Bestavros, Spyridon Braoudakis: Value-cognizant Speculative Concurrency Control. VLDB 1995: 122-133
  19. Atul Adya, Robert Gruber, Barbara Liskov, Umesh Maheshwari: Efficient Optimistic Concurrency Control Using Loosely Synchronized Clocks. SIGMOD Conference 1995: 23-34
  20. Piotr Krzyzagórski, Tadeusz Morzy: Optimistic Concurrency Control Algorithm with Dynamic Serialization Adjustment for Firm Deadline Real-Time Database Systems. ADBIS 1995: 27-42
  21. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Witold Litwin: Chronological Scheduling of Transactions with Temporal Dependencies. VLDB J. 3(1): 1-28(1994)
  22. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth: Using Tickets to Enforce the Serializability of Multidatabase Transactions. IEEE Trans. Knowl. Data Eng. 6(1): 166-180(1994)
  23. Jayant R. Haritsa, Michael J. Carey, Miron Livny: Value-Based Scheduling in Real-Time Database Systems. VLDB J. 2(2): 117-152(1993)
  24. Erhard Rahm: Empirical Performance Evaluation of Concurrency and Coherency Control Protocols for Database Sharing Systems. ACM Trans. Database Syst. 18(2): 333-377(1993)
  25. Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
  26. O. T. Satyanarayanan, Divyakant Agrawal: Efficient Execution of Read-Only Transactions in Replicated Multiversion Databases. IEEE Trans. Knowl. Data Eng. 5(5): 859-871(1993)
  27. Thomas F. Keefe, Wei-Tek Tsai, Jaideep Srivastava: Database Concurrency Control in Multilevel Secure Database Management Systems. IEEE Trans. Knowl. Data Eng. 5(6): 1039-1055(1993)
  28. Divyakant Agrawal, Soumitra Sengupta: Modular Synchronization in Distributed, Multiversion Databases: Version Control and Concurrency Control. IEEE Trans. Knowl. Data Eng. 5(1): 126-137(1993)
  29. Yoav Raz: Extended Commitment Ordering or Guaranteeing Global Serializability by Applying Commitment Order Selectivity to Global Transactions. PODS 1993: 83-96
  30. Sang Hyuk Son, Seok Park: Scheduling and Concurrency Control for Real-Time Database Systems. DASFAA 1993: 219-226
  31. Juhnyoung Lee, Sang Hyuk Son: An Optimistic Concurrency Control Protocol for Real-Time Database Systems. DASFAA 1993: 387-394
  32. Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992)
  33. Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992)
  34. B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 17(1): 163-199(1992)
  35. Divyakant Agrawal, Amr El Abbadi: The Generalized Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. ACM Trans. Database Syst. 17(4): 689-717(1992)
  36. Yoav Raz: The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Mangers Using Atomic Commitment. VLDB 1992: 292-312
  37. H. V. Jagadish, Oded Shmueli: Proclamation-Based Model for Cooperating Transactions. VLDB 1992: 265-276
  38. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: Using Delayed Commitment in Locking Protocols for Real-Time Databases. SIGMOD Conference 1992: 104-113
  39. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: An Approach to Eliminate Transaction Blocking in Locking Protocols. PODS 1992: 223-235
  40. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control for Epsilon-Serializability. ICDE 1992: 506-515
  41. Sang Hyuk Son, Seog Park, Yi Lin: An Integrated Real-Time Locking Protocol. ICDE 1992: 527-534
  42. Divyakant Agrawal, Amr El Abbadi: A Non-Restrictive Concurrency Control for Object Oriented Databases. EDBT 1992: 469-482
  43. Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991)
  44. Philip S. Yu, Hans-Ulrich Heiss, Daniel M. Dias: Modeling and Analysis of a Time-Stamp History Based Certification Protocol for Concurrency Control. IEEE Trans. Knowl. Data Eng. 3(4): 525-537(1991)
  45. K. Vidyasankar: A Non-Two Phase Locking Protocol for Global Concurrency Control in Distributed Heterogeneous Database Systems. IEEE Trans. Knowl. Data Eng. 3(2): 256-261(1991)
  46. Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991)
  47. Jiandong Huang, John A. Stankovic, Krithi Ramamritham, Donald F. Towsley: Experimental Evaluation of Real-Time Optimistic Concurrency Control Schemes. VLDB 1991: 35-46
  48. Divyakant Agrawal, V. Krishnamurthy: Using Multiversion Data for Non-interfering Execution of Write-only Transactions. SIGMOD Conference 1991: 98-107
  49. Tadashi Ohmori, Masaru Kitsuregawa, Hidehiko Tanaka: Scheduling Batch Transactions on Shared-Nothing Parallel Database Machines: Effects of Concurrency and Parallelism. ICDE 1991: 210-219
  50. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth: On Serializability of Multidatabase Transactions Through Forced Local Conflicts. ICDE 1991: 314-323
  51. Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990)
  52. Partha Dasgupta, Zvi M. Kedem: The Five Color Concurrency Control Protocol: Non-Two-Phase Locking in General Databases. ACM Trans. Database Syst. 15(2): 281-307(1990)
  53. W. Kevin Wilkinson, Marie-Anne Neimat: Maintaining Consistency of Client-Cached Data. VLDB 1990: 122-133
  54. David J. DeWitt, Philippe Futtersack, David Maier, Fernando Vélez: A Study of Three Alternative Workstation-Server Architectures for Object Oriented Database Systems. VLDB 1990: 107-121
  55. B. R. Badrinath, Krithi Ramamritham: Performance Evaluation of Semantics-based Multilevel Concurrency Control Protocols. SIGMOD Conference 1990: 163-172
  56. Jayant R. Haritsa, Michael J. Carey, Miron Livny: On Being Optimistic about Real-Time Constraints. PODS 1990: 331-343
  57. Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36
  58. Thomas F. Keefe, Wei-Tek Tsai, Jaideep Srivastava: Multilevel Secure Database Concurrency Control. ICDE 1990: 337-344
  59. Gail E. Kaiser: A Flexible Transaction Model for Software Engineering. ICDE 1990: 560-567
  60. Alok N. Choudhary: Cost of Distributed Deadlock Detection: A Performance Study. ICDE 1990: 174-181
  61. Matthew Bellew, Meichun Hsu, Va-On Tam: Update Propagation in Distributed Memory Hierarchy. ICDE 1990: 521-528
  62. Ulrich Herrmann, Peter Dadam, Klaus Küspert, E. A. Roman, Gunter Schlageter: A Lock Technique for Disjoint and Non-Disjoint Complex Objects. EDBT 1990: 219-237
  63. Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989)
  64. Bharat K. Bhargava, John Riedl: A Model for Adaptable Systems for Transaction Processing. IEEE Trans. Knowl. Data Eng. 1(4): 433-449(1989)
  65. Divyakant Agrawal, Soumitra Sengupta: Modular Synchronization in Multiversion Databases: versionControl and Concurrency Control. SIGMOD Conference 1989: 408-417
  66. William E. Weihl: The Impact of Recovery on Concurrency Control. PODS 1989: 259-269
  67. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  68. Calton Pu, Gail E. Kaiser, Norman C. Hutchinson: Split-Transactions for Open-Ended Activities. VLDB 1988: 26-37
  69. Jean-François Pons, Jean-François Vilarem: Mixed concurrency control: Dealing with heterogeneity in distributed database systems. VLDB 1988: 445-456
  70. Peter Peinl, Andreas Reuter, Harald Sammer: High Contention in a Stock Trading Database: A Case Study. SIGMOD Conference 1988: 260-268
  71. Akhil Kumar, Michael Stonebraker: Semantics Based Transaction Management Techniques for Replicated Data. SIGMOD Conference 1988: 117-125
  72. Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210
  73. Calton Pu: Superdatabases for Composition of Heterogeneous Databases. ICDE 1988: 548-555
  74. William Perrizo, Min Luo, Donald A. Varvel: Ordering Accesses to Improving Transaction Processing Performance. ICDE 1988: 58-63
  75. Cyril U. Orji, Leszek Lilien, Janusz Hyziak: A Performance Analysis of an Optimistic and a Basic Timestamp-Ordering Concurrency Control Algorithm for Centralized Database Systems. ICDE 1988: 64-71
  76. Ching-Liang Huang, Victor O. K. Li: A Quorum-Based Commit and Termination Protocol for Distributed Database Systems. ICDE 1988: 136-143
  77. Ahmed K. Elmagarmid, Abdelsalam Helal: Supporting Updates in Heterogeneous Distributed Database Systems. ICDE 1988: 564-569
  78. Mohan Ahuja, James C. Browne: Performance Evaluation of Two Concurrency Control Protocols for Distributed Databases with Multiversioned Entities. ICDE 1988: 426-436
  79. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
  80. Jerre D. Noe, David B. Wagner: Measured Performance of Time Interval Concurrency Control Techniques. VLDB 1987: 359-367
  81. Akhil Kumar, Michael Stonebraker: Performance Evaluation of an Operating System Transaction Manager. VLDB 1987: 473-481
  82. Kazuo Sugihara: Concurrency Control Based on Distributed Cycle Detection. ICDE 1987: 267-274
  83. J. Eliot B. Moss, Bruce Leban, Panos K. Chrysanthis: Finer Grained Concurrency for the Database Cache. ICDE 1987: 96-103
  84. Lin Chiu, Ming T. Liu: An Optimistic Concurrency Control Mechanism without Freezing for Distributed Database Systems. ICDE 1987: 322-329
  85. B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ICDE 1987: 304-311
  86. Mohan Ahuja, James C. Browne: Concurrency Control by Pre-Ordering Entities in Databases with Multi-Versioned Entities. ICDE 1987: 312-321
  87. Setrag Khoshafian, Patrick Valduriez: Sharing, Persistence, and Object-Orientation: A Database Perspective. DBPL 1987: 221-240
  88. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
  89. Philip S. Yu, Douglas W. Cornell, Daniel M. Dias, Balakrishna R. Iyer: On Affinity Based Routing in Multi-System Data Sharing. VLDB 1986: 249-256
  90. Meichun Hsu, Wei-Pang Yang: Concurrent Operations in Extendible Hashing. VLDB 1986: 241-247
  91. David R. Jefferson, Amihai Motro: The Time Warp Mechanism for Database Concurrency Control. ICDE 1986: 474-481
  92. Naoki Katoh, Toshihide Ibaraki, Tiko Kameda: Cautious Transaction Schedulers with Admission Control. ACM Trans. Database Syst. 10(2): 205-229(1985)
  93. Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985)
  94. Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985)
  95. Israel Gold, Oded Shmueli, Micha Hofri: The Private Workspace Model Feasibility and Applications to 2PL Performance Improvements. VLDB 1985: 192-208
  96. Wojciech Cellary, Tadeusz Morzy: Locking with Prevention of Cyclic and Infinite Restarting in Distributed Database Systems. VLDB 1985: 115-126
  97. Mukul K. Sinha, P. D. Nanadikar, S. L. Mehndiratta: Timestamp Based Certification Schemes for Transactions in Distributed Database Systems. SIGMOD Conference 1985: 402-411
  98. Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121
  99. Shridhar Acharya, Gael N. Buckley: Transaction Restarts in Prolog Database Systems. SIGMOD Conference 1985: 364-373
  100. Malcolm P. Atkinson, Peter Buneman, Ronald Morrison (Eds.): Data Types and Persistence. Edited Papers from the Proceedings of the First Workshop on Persistent Objects, Appin, Scotland, August 1985. Topics in Information Systems Springer 1988, ISBN 3-540-18785-5
  101. Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229
  102. Klaus Elhardt, Rudolf Bayer: A Database Cache for High Performance and Fast Restart in Database Systems. ACM Trans. Database Syst. 9(4): 503-525(1984)
  103. Michael Stonebraker, Lawrence A. Rowe: Database Portals: A New Application Program Interface. VLDB 1984: 3-13
  104. Ming-Yee Lai, W. Kevin Wilkinson: Distributed Transaction Management in Jasmin. VLDB 1984: 466-470
  105. Peter Dadam, Vincent Y. Lum, H.-D. Werner: Integration of Time Versions into a Relational Database System. VLDB 1984: 509-522
  106. Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118
  107. Claude Boksenbaum, Michèle Cart, Jean Ferrié, Jean-François Pons: Certification by Intervals of Timestamps in Distributed Database Systems. VLDB 1984: 377-387
  108. Daniel H. Fishman, Ming-Yee Lai, W. Kevin Wilkinson: Overview of the Jasmin Database Machine. SIGMOD Conference 1984: 234-239
  109. Haran Boral, Israel Gold: Towards A Self-Adapting Centralized Concurrency Control Algorithm. SIGMOD Conference 1984: 18-32
  110. Marc H. Graham, Nancy D. Griffeth, Barbara Smith-Thomas: Reliable Scheduling of Database Transactions for Unreliable Systems. PODS 1984: 300-310
  111. Toshimi Minoura, Kamran Parsaye: Version-Based Access Capabilities for Concurrency Control of a Database System. ICDE 1984: 300-306
  112. M. Dennis Mickunas, Pankaj Jalote, Roy H. Campbell: The Delay/Re-Read Protocol for Concurrency Control in Databases. ICDE 1984: 307-314
  113. Geneva G. Belford, Jane W.-S. Liu, D. Cho, P. Cotten, S. England, J. D. Goldstein, S. C. Hwung, K. A. Kaufman, C. K. Kim, J. Leo, A. P. Manolas, A. Moon, A. D. Smet, Y. L. Yan, L. Zhang, G. L. Robinson, R. L. Lapp: Mutual Consistency Maintenance in A Prototype Data Trafic Management System. ICDE 1984: 596-602
  114. Manuel Reimer: Solving the Phantom Problem by Predicative Optimistic Concurrency Control. VLDB 1983: 81-88
  115. Peter Peinl, Andreas Reuter: Empirical Comparison of Database Concurrency Schemes. VLDB 1983: 97-108
  116. Wen-Te K. Lin, Jerry Nolte: Basic Timestamp, Multiple Version Timestamp, and Two-Phase Locking. VLDB 1983: 109-119
  117. Michael J. Carey: An Abstract Model of Database Concurrency Control Algorithms. SIGMOD Conference 1983: 97-107
  118. Michael J. Carey: Granularity Hierarchies in Concurrency Control. PODS 1983: 156-165
  119. Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92
  120. Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
  121. M. R. Brown, R. G. G. Cattell, N. Suzuki: The Cedar DBMS: A Preliminary Report. SIGMOD Conference 1981: 205-211
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:45 2008