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)@article{DBLP:journals/tods/FranaszekR85,
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 = {http://doi.acm.org/10.1145/3148.3160, db/journals/tods/FranaszekR85.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
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.
CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [1]
- 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
- [2]
- Michael J. Carey:
Modeling and Evaluation of Database Concurrency Control Algorithms.
Ph.D. thesis, College of Engineering, University of California, Berkeley 1983
BibTeX
- [3]
- ...
- [4]
- ...
- [5]
- Jim Gray:
Notes on Data Base Operating Systems.
Advanced Course: Operating Systems 1978: 393-481 BibTeX
- [6]
- H. T. Kung, John T. Robinson:
On Optimistic Methods for Concurrency Control.
ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
- [7]
- A. M. Langer, Annie W. Shum:
The Distribution of Granule Accesses Made by Database Transactions.
Commun. ACM 25(11): 831-832(1982) BibTeX
- [8]
- Chin-Hwa Lee:
Queueing Analysis of Global Locking Synchronization Schemes for Multicopy Databases.
IEEE Trans. Computers 29(5): 371-384(1980) BibTeX
- [9]
- Wen-Te K. Lin:
Performance Evaluation of Two Concurrency Control Mechanisms in a Distributed Database System.
SIGMOD Conference 1981: 84-92 BibTeX
- [10]
- David B. Lomet:
Process Structuring, Synchronization, and Recovery Using Atomic Actions.
Language Design for Reliable Software 1977: 128-137 BibTeX
- [11]
- Dominique Potier, Ph. Leblanc:
Analysis of Locking Policies in Database Management Systems.
Commun. ACM 23(10): 584-593(1980) BibTeX
- [12]
- ...
- [13]
- 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
- [14]
- ...
Referenced by
- Alexander Thomasian:
Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing.
IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
- Alexander Thomasian:
Concurrency Control: Methods, Performance, and Analysis.
ACM Comput. Surv. 30(1): 70-119(1998)
- Kun-Lung Wu, Philip S. Yu, Calton Pu:
Divergence Control Algorithms for Epsilon Serializability.
IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
- Alexander Thomasian:
A Performance Comparison of Locking Methods with Limited Wait Depth.
IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
- Alexander Thomasian:
Checkpointing for Optimistic Concurrency Control Methods.
IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
- Alexander Thomasian:
On a More Realistic Lock Contention Model and Its Analysis.
ICDE 1994: 2-9
- V. Srinivasan, Michael J. Carey:
Performance of B+ Tree Concurrency Algorithms.
VLDB J. 2(4): 361-406(1993)
- Jayant R. Haritsa, Michael J. Carey, Miron Livny:
Value-Based Scheduling in Real-Time Database Systems.
VLDB J. 2(2): 117-152(1993)
- Alexander Thomasian:
Two-Phase Locking Performance and Its Thrashing Behavior.
ACM Trans. Database Syst. 18(4): 579-625(1993)
- Meichun Hsu, Bin Zhang:
Performance Evaluation of Cautious Waiting.
ACM Trans. Database Syst. 17(3): 477-512(1992)
- Peter A. Franaszek, John T. Robinson, Alexander Thomasian:
Concurrency Control for High Contention Environments.
ACM Trans. Database Syst. 17(2): 304-345(1992)
- 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
- Divyakant Agrawal, Amr El Abbadi, Richard Jeffers:
An Approach to Eliminate Transaction Blocking in Locking Protocols.
PODS 1992: 223-235
- Kun-Lung Wu, Philip S. Yu, Calton Pu:
Divergence Control for Epsilon-Serializability.
ICDE 1992: 506-515
- Alexander Thomasian:
Thrashing in Two-Phase Locking Revisited.
ICDE 1992: 518-526
- 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)
- Hans-Ulrich Heiss, Roger Wagner:
Adaptive Load Control in Transaction Processing Systems.
VLDB 1991: 47-54
- Wei-hsing Wang, Eugene Pinsky, Meichun Hsu:
Modeling Hot Spots In Database Systems.
PODS 1991: 82-91
- Alexander Thomasian:
Performance Limits of Two-Phase Locking.
ICDE 1991: 426-435
- Peter A. Franaszek, John T. Robinson, Alexander Thomasian:
Wait Depth Limited Concurrency Control.
ICDE 1991: 92-101
- Maurice Herlihy:
Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types.
ACM Trans. Database Syst. 15(1): 96-124(1990)
- Michael J. Carey, Sanjay Krishnamurthi, Miron Livny:
Load Control for Locking: The 'Half-and-Half' Approach.
PODS 1990: 72-84
- Philip S. Yu, Daniel M. Dias:
Concurrency Control Using Locking with Deferred Blocking.
ICDE 1990: 30-36
- Peter A. Franaszek, John T. Robinson, Alexander Thomasian:
Access Invariance and Its Use in High Contention Environments.
ICDE 1990: 47-55
- Alok N. Choudhary:
Cost of Distributed Deadlock Detection: A Performance Study.
ICDE 1990: 174-181
- Lubomir Bic, Robert L. Hartmann:
AGM: A Dataflow Database Machine.
ACM Trans. Database Syst. 14(1): 114-146(1989)
- 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)
- B. Paul Jenq, Brian C. Twichell, Tom W. Keller:
Locking Performance in a Shared Nothing Parallel Database Machine.
ICDE 1989: 149-158
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Rakesh Agrawal, Michael J. Carey, Miron Livny:
Concurrency Control Performance Modeling: Alternatives and Implications.
ACM Trans. Database Syst. 12(4): 609-654(1987)
- Jerre D. Noe, David B. Wagner:
Measured Performance of Time Interval Concurrency Control Techniques.
VLDB 1987: 359-367
- Akhil Kumar, Michael Stonebraker:
Performance Evaluation of an Operating System Transaction Manager.
VLDB 1987: 473-481
- Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley:
A Queueing Network Model for a Distributed Database Testbed System.
ICDE 1987: 62-71
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents - Rakesh Agrawal, Michael J. Carey, Miron Livny:
Models for Studying Concurrency Control Performance: Alternatives and Implications.
SIGMOD Conference 1985: 108-121
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:56 2008