Limitations of Concurrency in Transaction Processing.

Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985)
  author    = {Peter A. Franaszek and
               John T. Robinson},
  title     = {Limitations of Concurrency in Transaction Processing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {1},
  year      = {1985},
  pages     = {1-28},
  ee        = {, db/journals/tods/FranaszekR85.html},
  bibsource = {DBLP,}


Given the pairwise probability of conflict p among transactions in a transaction processing system, together with the total number of concurrent transactions n, the effective level of concurrency E(n,p) is defined as the expected number of the n transactions that can run concurrently and actually do useful work. Using a random graph model of concurrency, we show for three general classes of concurrency control methods, examples of which are (1) standard locking, (2) strict priority scheduling, and (3) optimistic methods, that (1) E(n, p) <= n(1 - p/2)n-1, (2) E(n, p) <= (1 - (1 - p)n)/p, and (3) 1 + ((1 - p)/p)ln(p(n - 1) + 1) <= E(n, p) <= 1 + (l/p)ln(p(n - 1) + 1). Thus, for fixed p, as n -> infinity, (1) E -> 0 for standard locking methods, (2) E <= 1/p for strict priority scheduling methods, and (3) E -> infinity for optimistic methods. Also found are bounds on E in the case where conflicts are analyzed so as to maximize E.

The predictions of the random graph model are confirmed by simulations of an abstract transaction processing system. In practice, though, there is a price to pay for the increased effective level of concurrency of methods (2) and (3): using these methods there is more wasted work (i.e., more steps executed by transactions that are later aborted). In response to this problem, three new concurrency control methods suggested by the random graph model analysis are developed. Two of these, called (a) running priority and (b) older or running priority, are shown by the simulation results to perform better than the previously known methods (1)-(3) for relatively large n or large p, in terms of achieving a high effective level of concurrency at a comparatively small cost in wasted work.

Copyright © 1985 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


Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985) BibTeX
Michael J. Carey: Modeling and Evaluation of Database Concurrency Control Algorithms. Ph.D. thesis, College of Engineering, University of California, Berkeley 1983
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
A. M. Langer, Annie W. Shum: The Distribution of Granule Accesses Made by Database Transactions. Commun. ACM 25(11): 831-832(1982) BibTeX
Chin-Hwa Lee: Queueing Analysis of Global Locking Synchronization Schemes for Multicopy Databases. IEEE Trans. Computers 29(5): 371-384(1980) BibTeX
Wen-Te K. Lin: Performance Evaluation of Two Concurrency Control Mechanisms in a Distributed Database System. SIGMOD Conference 1981: 84-92 BibTeX
David B. Lomet: Process Structuring, Synchronization, and Recovery Using Atomic Actions. Language Design for Reliable Software 1977: 128-137 BibTeX
Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX

Referenced by

  1. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
  2. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  3. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control Algorithms for Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
  4. Alexander Thomasian: A Performance Comparison of Locking Methods with Limited Wait Depth. IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
  5. Alexander Thomasian: Checkpointing for Optimistic Concurrency Control Methods. IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
  6. Alexander Thomasian: On a More Realistic Lock Contention Model and Its Analysis. ICDE 1994: 2-9
  7. V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
  8. Jayant R. Haritsa, Michael J. Carey, Miron Livny: Value-Based Scheduling in Real-Time Database Systems. VLDB J. 2(2): 117-152(1993)
  9. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
  10. Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992)
  11. Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Concurrency Control for High Contention Environments. ACM Trans. Database Syst. 17(2): 304-345(1992)
  12. Axel Mönkeberg, Gerhard Weikum: Performance Evaluation of an Adaptive and Robust Load Control Method for the Avoidance of Data-Contention Thrashing. VLDB 1992: 432-443
  13. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: An Approach to Eliminate Transaction Blocking in Locking Protocols. PODS 1992: 223-235
  14. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control for Epsilon-Serializability. ICDE 1992: 506-515
  15. Alexander Thomasian: Thrashing in Two-Phase Locking Revisited. ICDE 1992: 518-526
  16. 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)
  17. Hans-Ulrich Heiss, Roger Wagner: Adaptive Load Control in Transaction Processing Systems. VLDB 1991: 47-54
  18. Wei-hsing Wang, Eugene Pinsky, Meichun Hsu: Modeling Hot Spots In Database Systems. PODS 1991: 82-91
  19. Alexander Thomasian: Performance Limits of Two-Phase Locking. ICDE 1991: 426-435
  20. Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Wait Depth Limited Concurrency Control. ICDE 1991: 92-101
  21. Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990)
  22. Michael J. Carey, Sanjay Krishnamurthi, Miron Livny: Load Control for Locking: The 'Half-and-Half' Approach. PODS 1990: 72-84
  23. Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36
  24. Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Access Invariance and Its Use in High Contention Environments. ICDE 1990: 47-55
  25. Alok N. Choudhary: Cost of Distributed Deadlock Detection: A Performance Study. ICDE 1990: 174-181
  26. Lubomir Bic, Robert L. Hartmann: AGM: A Dataflow Database Machine. ACM Trans. Database Syst. 14(1): 114-146(1989)
  27. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared-Nothing Parallel Database Machine. IEEE Trans. Knowl. Data Eng. 1(4): 530-543(1989)
  28. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared Nothing Parallel Database Machine. ICDE 1989: 149-158
  29. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  30. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
  31. Jerre D. Noe, David B. Wagner: Measured Performance of Time Interval Concurrency Control Techniques. VLDB 1987: 359-367
  32. Akhil Kumar, Michael Stonebraker: Performance Evaluation of an Operating System Transaction Manager. VLDB 1987: 473-481
  33. Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley: A Queueing Network Model for a Distributed Database Testbed System. ICDE 1987: 62-71
  34. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
  35. Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121
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:56 2008