ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication.

Michael J. Carey, Miron Livny: Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication. VLDB 1988: 13-25
@inproceedings{DBLP:conf/vldb/CareyL88,
  author    = {Michael J. Carey and
               Miron Livny},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Distributed Concurrency Control Performance: A Study of Algorithms,
               Distribution, and Replication},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {13-25},
  ee        = {db/conf/vldb/CareyL88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Many concurrency control algorithms have been proposed for use in distributed database systems. Despite the large number of available algorithms, and the fact that distributed database systems are becoming a commercial reality, distributed concurrency control performance tradeoffs are still not well understood. In this paper we attempt to shed light on some of the important issues by studying four representative algorithms - distributed 2PL, wound-wait, basic timestamp ordering, and a distributed optimistic algorithm - using a detailed model of a distributed DBMS. We examine the performance of these algorithms for various levels of contention, "distributedness" of the workload, and data replication. The results should prove useful to designers of future distributed database systems.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
BibTeX

References

[Agra87]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX
[Bada79]
...
[Balt82]
R. Balter, P. Berard, Paul Decitre: Why Control of the Concurrency Level in Distributed Systems is More Fundamental Than Deadlock Management. PODC 1982: 183-193 BibTeX
[Bern80a]
...
[Bern80b]
Philip A. Bernstein, Nathan Goodman: Timestamp-Based Algorithms for Concurrency Control in Distributed Database Systems. VLDB 1980: 285-300 BibTeX
[Bern81]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[Bhar82]
...
[Care84]
Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118 BibTeX
[Care86]
Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119 BibTeX
[Ceri82]
Stefano Ceri, Susan S. Owicki: On the Use of Optimistic Methods for Concurrency Control in Distributed Databases. Berkeley Workshop 1982: 117-129 BibTeX
[DeWi86]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 BibTeX
[Gall82]
...
[Garc79]
...
[Gray79]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Kohl85]
...
[Lazo86]
Edward D. Lazowska, John Zahorjan, David R. Cheriton, Willy Zwaenepoel: File Access Performance of Diskless Workstations. ACM Trans. Comput. Syst. 4(3): 238-268(1986) BibTeX
[Li87]
Victor O. K. Li: Performance Models of Timestamp-Ordering Concurrency Control Algorithms in Distributed Databases. IEEE Trans. Computers 36(9): 1041-1051(1987) BibTeX
[Lin82]
Wen-Te K. Lin, Jerry Nolte: Performance of Two Phase Locking. Berkeley Workshop 1982: 131-160 BibTeX
[Lin83]
Wen-Te K. Lin, Jerry Nolte: Basic Timestamp, Multiple Version Timestamp, and Two-Phase Locking. VLDB 1983: 109-119 BibTeX
[Lind84]
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms, Robert A. Yost: Computation and Communication in R*: A Distributed Database Manager. ACM Trans. Comput. Syst. 2(1): 24-38(1984) BibTeX
[Livn88]
...
[Mena78]
Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Databases. Berkeley Workshop 1978: 215-232 BibTeX
[Noe87]
Jerre D. Noe, David B. Wagner: Measured Performance of Time Interval Concurrency Control Techniques. VLDB 1987: 359-367 BibTeX
[Ozsu85]
M. Tamer Özsu: Modeling and Analysis of Distributed Database Concurrency Control Algorithms Using an Extended Petri Net Formalism. IEEE Trans. Software Eng. 11(10): 1225-1240(1985) BibTeX
[Reed83]
David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) BibTeX
[Ries79]
Daniel R. Ries: The Effects of Concurrency Control on the Performance of a Distributed Data Management System. Berkeley Workshop 1979: 75-112 BibTeX
[Rose78]
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
[Schl81]
Gunter Schlageter: Optimistic Methods for Concurrency Control in Distributed Database Systems. VLDB 1981: 125-130 BibTeX
[Sinh85]
Mukul K. Sinha, P. D. Nanadikar, S. L. Mehndiratta: Timestamp Based Certification Schemes for Transactions in Distributed Database Systems. SIGMOD Conference 1985: 402-411 BibTeX
[Ston79]
Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) BibTeX
[Tera79]
...
[Thom79]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX
[Trai82]
Irving L. Traiger, Jim Gray, Cesare A. Galtieri, Bruce G. Lindsay: Transactions and Consistency in Distributed Database Systems. ACM Trans. Database Syst. 7(3): 323-342(1982) BibTeX

Referenced by

  1. Matthias Nicola, Matthias Jarke: Increasing the Expressiveness of Analytical Performance Models for Replicated Databases. ICDT 1999: 131-149
  2. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
  3. Vigyan Singhal, Alan Jay Smith: Analysis of Locking Behavior in Three Real Database Systems. VLDB J. 6(1): 40-52(1997)
  4. Ramesh Gupta, Jayant R. Haritsa, Krithi Ramamritham: Revisiting Commit Processing in Distributed Database Systems. SIGMOD Conference 1997: 486-497
  5. Yixiu Huang, A. Prasad Sistla, Ouri Wolfson: Data Replication for Mobile Computers. SIGMOD Conference 1994: 13-24
  6. Eui Kyeong Hong: Performance of Catalog Management Schemes for Running Access Modules in a Locally Distributed Database System. VLDB 1993: 194-205
  7. Yixiu Huang, Ouri Wolfson: A Competitive Dynamic Data Replication Algorithm. ICDE 1993: 310-317
  8. Shun Yan Cheung, Mostafa H. Ammar, Mustaque Ahamad: The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. IEEE Trans. Knowl. Data Eng. 4(6): 582-592(1992)
  9. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
  10. Michael J. Carey, Rajiv Jauhari, Miron Livny: On Transaction Boundaries in Active Databases: A Performance Perspective. IEEE Trans. Knowl. Data Eng. 3(3): 320-336(1991)
  11. Yongdong Wang, Lawrence A. Rowe: Cache Consistency and Concurrency Control in a Client/Server DBMS Architecture. SIGMOD Conference 1991: 367-376
  12. Bruno Ciciani, Daniel M. Dias, Philip S. Yu: Analysis of Replication in Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 2(2): 247-261(1990)
  13. Jayant R. Haritsa, Michael J. Carey, Miron Livny: On Being Optimistic about Real-Time Constraints. PODS 1990: 331-343
  14. Matthew Bellew, Meichun Hsu, Va-On Tam: Update Propagation in Distributed Memory Hierarchy. ICDE 1990: 521-528
  15. 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)
  16. Michael J. Carey, Miron Livny: Parallelism and Concurrency Control Performance in Distributed Database Machines. SIGMOD Conference 1989: 122-133
  17. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared Nothing Parallel Database Machine. ICDE 1989: 149-158
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:37 2009