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

[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

[ABG]

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

[Badal]

...

[BEHR]

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

[BHR]

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

[BG1]

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

[BG2]

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

[BGL]

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

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

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

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

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

[Casa]

...

[CB]

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

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

[Dubo]

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

[Ellis]

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

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

[G-M1]

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

[G-M2]

...

[G-M3]

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

[GS]

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

[GlSh]

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

[Giff]

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

[Gray]

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

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

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

[Holt]

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

[KNTH]

...

[KP1]

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

[KP2]

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

[KMIT]

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

[KC]

...

[KR]

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

[Lamp]

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

[LS]

...

[Lee]

...

[Lelann]

...

[Lin]

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

[LN]

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

[Lomet1]

...

[Lomet2]

...

[Lomet3]

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

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

[MN1]

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

[MN2]

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

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

[Mino]

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

[Montgomery]

...

[PBR]

...

[Papadimitriou]

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

[PK]

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

[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

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

[SM]

...

[SK]

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

[SRL]

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

[SR]

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

[Stonebraker]

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

[Thom]

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