ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Concurrency Control in Distributed Database Systems.

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
@article{DBLP:journals/csur/BernsteinG81,
  author    = {Philip A. Bernstein and
               Nathan Goodman},
  title     = {Concurrency Control in Distributed Database Systems},
  journal   = {ACM Comput. Surv.},
  volume    = {13},
  number    = {2},
  year      = {1981},
  pages     = {185-221},
  ee        = {db/journals/csur/BernsteinG81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we survey, consolidate, and present the state of the art in distributed database concurrency control. The heart of our analysis is a decomposition of the concurrency control problem into two major subproblems: read-write and write-write synchronization. We describe a series of synchronization techniques for solving each subproblem and show how to combine these techniques into algorithms for solving the entire concurrency control problem. Such algorithms are called "concurrency control methods". We describe 48 principal methods, including all practical algorithms that have appeared in the literature plus several new ones. We concentrate on the structure and correctnees of concurrency control algorithms. Issues of performance are given only secondary treatment.

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.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Online Edition: ACM Digital Library


References

[Aho75]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Alsb76a]
Peter Alsberg, J. D. Day: A Principle for Resilient Sharing of Distributed Resources. ICSE 1976: 562-570 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Alsb76b]
...
[Bada78]
Dushan Z. Badal, Gerald J. Popek: A Proposal for Distributed Concurrency Control for Partially Redundant Distributed Data Base Systems. Berkeley Workshop 1978: 273-285 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bada79]
...
[Bada80]
Dushan Z. Badal: On the Degree of Concurrency Provided by Concurrency Control Mechanisms for Distributed Databases. DDB 1980: 35-48 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Baye80]
Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Belf76]
...
[Bern78a]
Philip A. Bernstein, James B. Rothnie Jr., Nathan Goodman, Christos H. Papadimitriou: The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case). IEEE Trans. Software Eng. 4(3): 154-168(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bern79a]
...
[Bern79b]
Philip A. Bernstein, David W. Shipman, Wing S. Wong: Formal Aspects of Serializability in Database Concurrency Control. IEEE Trans. Software Eng. 5(3): 203-216(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bern80a]
Philip A. Bernstein, Nathan Goodman: Timestamp-Based Algorithms for Concurrency Control in Distributed Database Systems. VLDB 1980: 285-300 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bern80b]
Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bern80c]
Philip A. Bernstein, David W. Shipman: The Correctness of Concurrency Control Mechanisms in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 52-68(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bern80d]
Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bern81]
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Brei79]
H. Breitwieser, U. Kersten: Transaction and Catalog Management of the Distributed File Management System DISCO. VLDB 1979: 340-350 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Brin73]
...
[Casa79]
...
[Cham74]
Donald D. Chamberlin, Raymond F. Boyce, Irving L. Traiger: A Deadlock-Free Scheme for Resource Locking in a Data-Base Environment. IFIP Congress 1974: 340-343 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chen80]
Wing Kai Cheng, Geneva G. Belford: Update Synchronization in Distributed Databases. VLDB 1980: 301-308 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Depp76]
Mark Deppe, James P. Fry: Distributed Data Bases; A Summary of Research. Computer Networks 1: 130-138(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dijk71]
Edsger W. Dijkstra: Hierarchical Ordering of Sequential Processes. Acta Inf. 1: 115-138(1971) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Elli77]
Clarence A. Ellis: A Robust Algorithm for Updating Duplicate Databases. Berkeley Workshop 1977: 146-158 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Eswa76]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Garc78]
Hector Garcia-Molina: Performance Comparison of Two Update Algorithms for Distributed Databases. Berkeley Workshop 1978: 108-119 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Garc79a]
...
[Garc79b]
Hector Garcia-Molina: A Concurrency Control Mechanism for Distributed Databases Which Users Centralized Locking Controllers. Berkeley Workshop 1979: 113- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Garc79c]
...
[Gard77]
Georges Gardarin, P. Lebeux: Scheduling Algorithms for Avoiding Inconsistency in Large Databases. VLDB 1977: 501-506 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gele78]
Erol Gelenbe, Kenneth C. Sevcik: Analysis of Update Synchronization for Multiple Copy Data-Bases. Berkeley Workshop 1978: 69-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Giff79]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gray75]
Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger: Granularity of Locks and Degrees of Consistency in a Shared Data Base. IFIP Working Conference on Modelling in Data Base Management Systems 1976: 365-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gray78]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hamm80]
Michael Hammer, David W. Shipman: Reliability Mechanisms for SDD-1: A System for Distributed Databases. ACM Trans. Database Syst. 5(4): 431-466(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hewi74]
...
[Hoar74]
C. A. R. Hoare: Monitors: An Operating System Structuring Concept. Commun. ACM 17(10): 549-557(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Holt72]
Richard C. Holt: Some Deadlock Properties of Computer Systems. ACM Comput. Surv. 4(3): 179-196(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kane79]
...
[Kawa79]
Seiichi Kawazu, Susumu Minami, Kenji Itoh, Katsuni Teranaka: Two-Phase Deadlock Detection Algorithm in Distributed Databases. VLDB 1979: 360-367 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[King74]
...
[Kung79]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kung81]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lamp76]
...
[Lamp78]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lela78]
Gérard Le Lann: Algorithms for Distributed Data-Sharing Systems Which Use Tickets. Berkeley Workshop 1978: 259-272 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lin79]
Wen-Te K. Lin: Concurrency Control in a Multiple Copy Distributed Database System. Berkeley Workshop 1979: 207-220 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mena79]
Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mena80]
Daniel A. Menascé, Gerald J. Popek, Richard R. Muntz: A Locking Protocol for Resource Coordination in Distributed Databases. ACM Trans. Database Syst. 5(2): 103-138(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mino78]
Toshimi Minoura: Maximally Concurrent Transaction Processing. Berkeley Workshop 1978: 206-214 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mino79]
Toshimi Minoura: A New Concurrency Control Algorithm for Distributed Database Systems. Berkeley Workshop 1979: 221- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mont78]
...
[Papa77]
...
[Papa79]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rahi79]
...
[Rami79]
Raúl J. Ramírez, Nicola Santoro: Distributed Control of Updates in Multiple-Copy Databases: A Time Optimal Algorithm. Berkeley Workshop 1979: 191- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Reed78]
...
[Reis79a]
...
[Reis79b]
Daniel R. Ries: The Effects of Concurrency Control on the Performance of a Distributed Data Management System. Berkeley Workshop 1979: 75-112 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rose79]
Eric C. Rosen: The Updating Protocol of the ARPANET's New Routing Algorithm: A Case Study in Maintaining Identical Copies of a Changing Distributed Data Base. Berkeley Workshop 1979: 260- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Roth77]
James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Schl78]
Gunter Schlageter: Process Synchronization in Database Systems. ACM Trans. Database Syst. 3(3): 248-271(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sequ79]
...
[Shap77a]
...
[Shap77b]
...
[Silb80]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Stea76]
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Stea81]
Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ston77]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ston79]
Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Thom79]
...
[Verh78]
Joost Verhofstad: Recovery and Carsh Resistance in a Filing System. SIGMOD Conference 1977: 158-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:26:19 2010 by Michael Ley (ley@uni-trier.de)