A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper).

@inproceedings{DBLP:conf/vldb/BernsteinG82,
  author    = {Philip A. Bernstein and
               Nathan Goodman},
  title     = {A Sophisticate's Introduction to Distributed Concurrency Control
               (Invited Paper)},
  booktitle = {Eigth International Conference on Very Large Data Bases, September
               8-10, 1982, Mexico City, Mexico, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1982},
  isbn      = {0-934613-14-1},
  pages     = {62-76},
  ee        = {db/conf/vldb/BernsteinG82.html},
  crossref  = {DBLP:conf/vldb/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Dozens of articles have been published describing "new" concurrency control algorithms for distributed database systems. All of these algorithms can be derived and understood using a few basic concepts. We show how to decompose the concurrency control problem into several subproblems, each of which has iust a few known solutions. By appropriately combining known solutions to the subproblems, we show that all published concurrency control algorithms and many new ones can be constructed. The glue that binds the subproblems and solutions together is a mathematical theory known as serializability theory.

This paper does not assume previous knowledge of distributed database concurrency control algorithms, and is suitable for both the uninitiated and the cognoscente.

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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD 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/vldb7588 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/aDVD1 or /dvd

Printed Edition

References

[AD]

Peter Alsberg, J. D. Day: A Principle for Resilient Sharing of Distributed Resources. ICSE 1976: 562-570 BibTeX

[AHU]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[ABG]

Rony Attar, Philip A. Bernstein, Nathan Goodman: Site Initialization, Recovery, and Back-Up in a Distributed Database System. Berkeley Workshop 1982: 185-202 BibTeX

[Badal]

...

[BEHR]

Rudolf Bayer, Klaus Elhardt, Hans Heller, Angelika Reiser: Distributed Concurrency Control in Database Systems. VLDB 1980: 275-284 BibTeX

[BHR]

Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980) BibTeX

[BG1]

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX

[BG2]

Arthur J. Bernstein, Nathan Goodman: Concurrency Control Algorithms for Multiversion Database Systems. PODC 1982: 209-215 BibTeX

[BGL]

Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 BibTeX

[BRGP]

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) BibTeX

[BS]

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) BibTeX

[BSR]

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) BibTeX

[BSW]

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) BibTeX

[Casa]

...

[CB]

Wing Kai Cheng, Geneva G. Belford: Update Synchronization in Distributed Databases. VLDB 1980: 301-308 BibTeX

[CGP]

Edward G. Coffman Jr., Erol Gelenbe, Brigitte Plateau: Optimization of the Number of Copies in a Distributed Data Base. IEEE Trans. Software Eng. 7(1): 78-84(1981) BibTeX

[Dubo]

Deborah DuBourdieux: Implementation of Distributed Transactions. Berkeley Workshop 1982: 81-94 BibTeX

[Ellis]

Clarence A. Ellis: A Robust Algorithm for Updating Duplicate Databases. Berkeley Workshop 1977: 146-158 BibTeX

[EGLT]

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

[G-M1]

Hector Garcia-Molina: Performance Comparison of Two Update Algorithms for Distributed Databases. Berkeley Workshop 1978: 108-119 BibTeX

[G-M2]

...

[G-M3]

Hector Garcia-Molina: A Concurrency Control Mechanism for Distributed Databases Which Users Centralized Locking Controllers. Berkeley Workshop 1979: 113- BibTeX

[GS]

Erol Gelenbe, Kenneth C. Sevcik: Analysis of Update Synchronization for Multiple Copy Data-Bases. Berkeley Workshop 1978: 69-90 BibTeX

[GlSh]

Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) BibTeX

[Giff]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[Gray]

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

[GLPT]

...

[GMBL]

Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX

[HS]

Michael Hammer, David W. Shipman: Reliability Mechanisms for SDD-1: A System for Distributed Databases. ACM Trans. Database Syst. 5(4): 431-466(1980) BibTeX

[Holt]

Richard C. Holt: Some Deadlock Properties of Computer Systems. ACM Comput. Surv. 4(3): 179-196(1972) BibTeX

[KNTH]

...

[KP1]

Paris C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? PODS 1982: 98-107 BibTeX

[KP2]

Paris C. Kanellakis, Christos H. Papadimitriou: The Complexity of Distributed Concurrency Control. FOCS 1981: 185-197 BibTeX

[KMIT]

Seiichi Kawazu, Susumu Minami, Kenji Itoh, Katsuni Teranaka: Two-Phase Deadlock Detection Algorithm in Distributed Databases. VLDB 1979: 360-367 BibTeX

[KC]

...

[KR]

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. VLDB 1979: 351 BibTeX

[Lamp]

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX

[LS]

...

[Lee]

...

[Lelann]

...

[Lin]

Wen-Te K. Lin: Concurrency Control in a Multiple Copy Distributed Database System. Berkeley Workshop 1979: 207-220 BibTeX

[LN]

Wen-Te K. Lin, Jerry Nolte: Performance of Two Phase Locking. Berkeley Workshop 1982: 131-160 BibTeX

[Lomet1]

...

[Lomet2]

...

[Lomet3]

David B. Lomet: Subsystems of Processes with Deadlock Avoidance. IEEE Trans. Software Eng. 6(3): 297-304(1980) BibTeX

[Lomet4]

...

[MM]

Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979) BibTeX

[MN1]

Daniel A. Menascé, Tatuo Nakanishi: Optimistic versus pessimistic concurrency control mechanisms in database management systems. Inf. Syst. 7(1): 13-27(1982) BibTeX

[MN2]

Daniel A. Menascé, Tatuo Nakanishi: Performance Evaluation of a Two-Phase Commit Based Protocol for DDBS. PODS 1982: 247-255 BibTeX

[MPM]

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) BibTeX

[Mino]

Toshimi Minoura: A New Concurrency Control Algorithm for Distributed Database Systems. Berkeley Workshop 1979: 221- BibTeX

[Montgomery]

...

[PBR]

...

[Papadimitriou]

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

[PK]

Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. PODS 1982: 76-82 BibTeX

[Reed]

...

[Ries1]

...

[Ries2]

Daniel R. Ries: The Effects of Concurrency Control on the Performance of a Distributed Data Management System. Berkeley Workshop 1979: 75-112 BibTeX

[RSL]

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

[SM]

...

[SK]

Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX

[SRL]

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

[SR]

Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83 BibTeX

[Stonebraker]

Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) BibTeX

[Thom]

Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX

Referenced by

1. Scott T. Leutenegger, Daniel M. Dias: A Modeling Study of the TPC-C Benchmark. SIGMOD Conference 1993: 22-31
2. 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)
3. Uwe M. Borghoff: Voting and Relocation Strategies Preserving Consistency among Replicated Files. ICDT 1990: 318-332
4. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
5. Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley: A Queueing Network Model for a Distributed Database Testbed System. ICDE 1987: 62-71
6. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
   Contents
7. Thanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. PODS 1986: 43-46
8. K. H. Pun, Geneva G. Belford: Optimal Granularity and Degree of Multiprogramming in a Distributed Database System. ICDE 1986: 13-20
9. David R. Jefferson, Amihai Motro: The Time Warp Mechanism for Database Concurrency Control. ICDE 1986: 474-481
10. Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985)
11. Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121
12. Philip A. Bernstein, Nathan Goodman: An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases. ACM Trans. Database Syst. 9(4): 596-615(1984)
13. Kari-Jouko Räihä, Henry Tirri: Towards a Theory of Online Schedulers. PODS 1984: 323-332
14. Michael J. Carey: An Abstract Model of Database Concurrency Control Algorithms. SIGMOD Conference 1983: 97-107
15. Nathan Goodman, Dale Skeen, Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: A Recovery Algorithm for a Distributed Database System. PODS 1983: 8-15
16. Michael J. Carey: Granularity Hierarchies in Concurrency Control. PODS 1983: 156-165