ACM SIGMOD Anthology TODS dblp.uni-trier.de

System Level Concurrency Control for Distributed Database Systems.

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)
@article{DBLP:journals/tods/RosenkrantzSL78,
  author    = {Daniel J. Rosenkrantz and
               Richard Edwin Stearns and
               Philip M. Lewis II},
  title     = {System Level Concurrency Control for Distributed Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {3},
  number    = {2},
  year      = {1978},
  pages     = {178-198},
  ee        = {http://doi.acm.org/10.1145/320251.320260, db/journals/tods/RosenkrantzSL78.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A distributed database system is one in which the database is spread among several sites and application programs "move" from site to site to access and update the data they need. The concurrency control is that portion of the system that responds to the read and write requests of the application programs. Its job is to maintain the global consistency of the distributed database while ensuring that the termination of the application programs is not prevented by phenomena such as deadlock. We assume each individual site has its own local concurrency control which responds to requests at that site and can only communicate with concurrency controls at other sites when an application program moves from site to site, terminates, or aborts.

This paper presents designs for several distributed concurrency controls and demonstrates that they work correctly. It also investigates some of the implications of global consistency of a distributed database and discusses phenomena that can prevent termination of application programs.

Copyright © 1978 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

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]
...
[2]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[3]
Rudolf Bayer: On the Integrity of Data Bases and Resource Locking. IBM Symposium: Data Base Systems 1975: 339-361 BibTeX
[4]
...
[5]
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 BibTeX
[6]
...
[7]
Edward G. Coffman Jr., M. J. Elphick, Arie Shoshani: System Deadlocks. ACM Comput. Surv. 3(2): 67-78(1971) BibTeX
[8]
Pierre-Jacques Courtois, F. Heymans, David Lorge Parnas: Concurrent Control with "Readers" and "Writers". Commun. ACM 14(10): 667-668(1971) BibTeX
[9]
...
[10]
...
[11]
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
[12]
...
[13]
...
[14]
...
[15]
...
[16]
Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger: Granularity of Locks in a Large Shared Data Base. VLDB 1975: 428-451 BibTeX
[17]
...
[18]
D. A. Hawley, J. S. Knowles, E. E. Tozer: Database Consistency and the CODASYL DBTG Proposals. Comput. J. 18(3): 206-212(1975) BibTeX
[19]
C. A. R. Hoare: Monitors: An Operating System Structuring Concept. Commun. ACM 17(10): 549-557(1974) BibTeX
[20]
...
[21]
...
[22]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[23]
Philip P. Macri: Deadlock Detection and Resolution in a CODASYL Based Data Management System. SIGMOD Conference 1976: 45-49 BibTeX
[24]
Gunter Schlageter: Access Synthronization and Deadlock-Analysis in Database Systems: An Implementation-oriented Approach. Inf. Syst. 1(3): 97-102(1975) BibTeX
[25]
Lucia C. Sekino: Multiple Concurrent Updates. VLDB 1975: 505-507 BibTeX
[26]
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX
[27]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 BibTeX

Referenced by

  1. Makoto Yokoo, Edmund H. Durfee, Toru Ishida, Kazuhiro Kuwabara: The Distributed Constraint Satisfaction Problem: Formalization and Algorithms. IEEE Trans. Knowl. Data Eng. 10(5): 673-685(1998)
  2. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
  3. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  4. Alexander Thomasian: A Performance Comparison of Locking Methods with Limited Wait Depth. IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
  5. Chang S. Keum, Wan Choi, Eui Kyeong Hong, Won-Young Kim, Kyu-Young Whang: Performance Evaluation of Replica Control Algorithms in a Locally Distributed Database System. DASFAA 1995: 388-396
  6. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth: Using Tickets to Enforce the Serializability of Multidatabase Transactions. IEEE Trans. Knowl. Data Eng. 6(1): 166-180(1994)
  7. Divyakant Agrawal, John L. Bruno, Amr El Abbadi, Vashudha Krishnaswamy: Relative Serializbility: An Approach for Relaxing the Atomicity of Transactions. PODS 1994: 139-149
  8. Theo Härder, Kurt Rothermel: Concurrency Control Issues in Nested Transactions. VLDB J. 2(1): 39-74(1993)
  9. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
  10. F. Bukhari, Sylvia L. Osborn: Two Fully Distributed Concurrency Control Algorithms. IEEE Trans. Knowl. Data Eng. 5(5): 872-881(1993)
  11. Eui Kyeong Hong: Performance of Catalog Management Schemes for Running Access Modules in a Locally Distributed Database System. VLDB 1993: 194-205
  12. Yuri Breitbart, Abraham Silberschatz, Glenn R. Thompson: Transaction Management Issues in a Failure-Prone Multidatabase System Environment. VLDB J. 1(1): 1-39(1992)
  13. Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992)
  14. Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991)
  15. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
  16. 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)
  17. Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991)
  18. Partha Dasgupta, Zvi M. Kedem: The Five Color Concurrency Control Protocol: Non-Two-Phase Locking in General Databases. ACM Trans. Database Syst. 15(2): 281-307(1990)
  19. Yuri Breitbart, Abraham Silberschatz, Glenn R. Thompson: Reliable Transaction Management in a Multidatabase System. SIGMOD Conference 1990: 215-224
  20. Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36
  21. Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989)
  22. 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)
  23. Michael J. Carey, Miron Livny: Parallelism and Concurrency Control Performance in Distributed Database Machines. SIGMOD Conference 1989: 122-133
  24. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared Nothing Parallel Database Machine. ICDE 1989: 149-158
  25. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  26. Michael J. Carey, Miron Livny: Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication. VLDB 1988: 13-25
  27. William Perrizo, Min Luo, Donald A. Varvel: Ordering Accesses to Improving Transaction Processing Performance. ICDE 1988: 58-63
  28. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
  29. L. Edwin McKenzie, Richard T. Snodgrass: Extending the Relational Algebra to Support Transaction Time. SIGMOD Conference 1987: 467-478
  30. Vassos Hadzilacos: A Knowledge Theoretic Analysis of Atomic Commitment Protocols. PODS 1987: 129-134
  31. Lin Chiu, Ming T. Liu: An Optimistic Concurrency Control Mechanism without Freezing for Distributed Database Systems. ICDE 1987: 322-329
  32. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  33. Nancy A. Lynch, Michael Merritt: Introduction to the Theory of Nested Transactions. ICDT 1986: 278-305
  34. Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985)
  35. Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985)
  36. Wojciech Cellary, Tadeusz Morzy: Locking with Prevention of Cyclic and Infinite Restarting in Distributed Database Systems. VLDB 1985: 115-126
  37. Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121
  38. Ouri Wolfson, Mihalis Yannakakis: Deadlock-Freedom (and Safety) of Transactions in a Distributed Database. PODS 1985: 105-112
  39. Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118
  40. Claude Boksenbaum, Michèle Cart, Jean Ferrié, Jean-François Pons: Certification by Intervals of Timestamps in Distributed Database Systems. VLDB 1984: 377-387
  41. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
  42. Toshimi Minoura, Kamran Parsaye: Version-Based Access Capabilities for Concurrency Control of a Database System. ICDE 1984: 300-306
  43. Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983)
  44. Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983)
  45. Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983)
  46. Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983)
  47. Wen-Te K. Lin, Jerry Nolte: Basic Timestamp, Multiple Version Timestamp, and Two-Phase Locking. VLDB 1983: 109-119
  48. Werner Kießling, G. Landherr: A Quantitative Comparison of Lockprotocols for Centralized Databases. VLDB 1983: 120-130
  49. Partha Dasgupta, Zvi M. Kedem: A Non-Two-Phase Locking Protocol for Concurrency Control in General Databases. VLDB 1983: 92-94
  50. Michael J. Carey: An Abstract Model of Database Concurrency Control Algorithms. SIGMOD Conference 1983: 97-107
  51. 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
  52. Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. PODS 1983: 1-7
  53. Michael J. Carey: Granularity Hierarchies in Concurrency Control. PODS 1983: 156-165
  54. 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)
  55. Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982)
  56. Zvi M. Kedem, C. Mohan, Abraham Silberschatz: An Efficient Deadlock Removal Scheme for Non-Two-Phase Locking Protocols. VLDB 1982: 91-97
  57. Arlette Ferrier, Christine Stangret: Heterogeneity in the Distributed Database Management System SIRIUS-DELTA. VLDB 1982: 45-53
  58. Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper). VLDB 1982: 62-76
  59. Herbert Kuss: On Totally Ordering Checkpoints in Distributed Data Bases. SIGMOD Conference 1982: 174, 293-302
  60. Eric C. Cooper: Analysis of Distributed Commit Protocols. SIGMOD Conference 1982: 175-183
  61. C. Mohan, Donald S. Fussell, Abraham Silberschatz: Compatibility and Commutativity in Non-two-phase Locking Protocols. PODS 1982: 283-292
  62. Daniel A. Menascé, Tatuo Nakanishi: Performance Evaluation of a Two-Phase Commit Based Protocol for DDBS. PODS 1982: 247-255
  63. Nancy A. Lynch: Multilevel Atomicity. PODS 1982: 63-69
  64. Paris C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? PODS 1982: 98-107
  65. A. James Baroody Jr., David J. DeWitt: An Object-Oriented Approach to Database System Implementation. ACM Trans. Database Syst. 6(4): 576-601(1981)
  66. Walter H. Kohler: A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems. ACM Comput. Surv. 13(2): 149-183(1981)
  67. Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
  68. Jim Gray: The Transaction Concept: Virtues and Limitations (Invited Paper). VLDB 1981: 144-154
  69. Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: A Theory of Correct Locking Protocols for Database Systems. VLDB 1981: 112-124
  70. Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83
  71. Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: Deadlock Removal Using Partial Rollback in Database Systems. SIGMOD Conference 1981: 65-73
  72. 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)
  73. Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980)
  74. Zvi M. Kedem, Abraham Silberschatz: Non-Two-Phase Locking Protocols with Shared and Exclusive Locks. VLDB 1980: 309-317
  75. Wing Kai Cheng, Geneva G. Belford: Update Synchronization in Distributed Databases. VLDB 1980: 301-308
  76. Rudolf Bayer, Klaus Elhardt, Hans Heller, Angelika Reiser: Distributed Concurrency Control in Database Systems. VLDB 1980: 275-284
  77. Dushan Z. Badal: The Analysis of the Effects of Concurrency Control on Distributed Database System Performance. VLDB 1980: 376-383
  78. C. J. Date: Locking and Recovery in a Shared Database System: An Application Programming Tutorial. VLDB 1979: 1-15
  79. Keki B. Irani, Hing-Lung Lin: Queuing Network Models for Concurrent Transaction Processing in a Database System. SIGMOD Conference 1979: 134-142
  80. James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62
  81. K. Mani Chandy: Models of Distributed Systems. VLDB 1977: 105-120
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:38 2008