On Optimistic Methods for Concurrency Control.

@article{DBLP:journals/tods/KungR81,
  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        = {http://doi.acm.org/10.1145/319566.319567, db/journals/tods/KungR81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[2]

Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX

[3]

Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX

[4]

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

[5]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[6]

H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX

[7]

H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX

[8]

...

[9]

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX

[10]

...

[11]

...

[12]

Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX

[13]

Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX

[14]

Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

[15]

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
    Contents
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
    Contents
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
     Contents
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