Achieving Robustness in Distributed Database Systems.

@article{DBLP:journals/tods/EagerS83,
  author    = {Derek L. Eager and
               Kenneth C. Sevcik},
  title     = {Achieving Robustness in Distributed Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {3},
  year      = {1983},
  pages     = {354-381},
  ee        = {http://doi.acm.org/10.1145/319989.319992, db/journals/tods/EagerS83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem of concurrency control in distributed database systems in which site and communication link failures may occur is considered. The possible range of failures is not restricted; in particular, failures may induce an arbitrary network partitioning. It is desirable to attain a high "level of robustness" in such a system; that is, these failures should have only a small impact on system operation.

A level of robustness termed maximal partial operability is identified. Under our models of concurrency control and robustness, this robustness level is the highest level attainable without significantly degrading performance.

A basis for the implementation of maximal partial operability is presented. To illustrate its use, it is applied to a distributed locking concurrency control method and to a method that utilizes timestamps. When no failures are present, the robustness modifications for these methods induce no significant additional overhead.

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

• 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/An3-1 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/aDVD2 or /dvd

References

[1]

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

[2]

Dushan Z. Badal, Gerald J. Popek: A Proposal for Distributed Concurrency Control for Partially Redundant Distributed Data Base Systems. Berkeley Workshop 1978: 273-285 BibTeX

[3]

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

[4]

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

[5]

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

[6]

...

[7]

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

[8]

...

[9]

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

[10]

...

[11]

Erol Gelenbe, Kenneth C. Sevcik: Analysis of Update Synchronization for Multiple Copy Data Bases. IEEE Trans. Computers 28(10): 737-747(1979) BibTeX

[12]

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

[13]

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

[14]

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

[15]

...

[16]

H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX

[17]

...

[18]

Wen-Te K. Lin: Performance Evaluation of Two Concurrency Control Mechanisms in a Distributed Database System. SIGMOD Conference 1981: 84-92 BibTeX

[19]

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

[20]

...

[21]

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

[22]

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

[23]

Dale Skeen: Nonblocking Commit Protocols. SIGMOD Conference 1981: 133-142 BibTeX

[24]

Dale Skeen: A Quorum-Based Commit Protocol. Berkeley Workshop 1982: 69-80 BibTeX

[25]

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

[26]

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

[27]

M. J. Stucki, Jerome R. Cox Jr., Gruia-Catalin Roman, P. N. Turcu: Coordinating Concurrent Access in a Distributed Database Architecture. Computer Architecture for Non-Numeric Processing 1978: 60-64 BibTeX

[28]

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. Peter Triantafillou, David J. Taylor: VELOS: A New Approach for Efficiently Achieving High Availability in Partitioned Distributed Systems. IEEE Trans. Knowl. Data Eng. 8(2): 305-321(1996)
2. Kenneth J. Goldman, Nancy A. Lynch: Quorum Consensus in Nested Transaction Systems. ACM Trans. Database Syst. 19(4): 537-585(1994)
3. A. B. Stephens, Yelena Yesha, Keith E. Humenik: Optimal Allocation for Partially Replicated Database Systems on Ring Networks. IEEE Trans. Knowl. Data Eng. 6(6): 975-982(1994)
4. Nabil R. Adam: A New Dynamic Voting Algorithm for Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 6(3): 470-478(1994)
5. Ada Wai-Chee Fu, David Wai-Lok Cheung: A Transaction Replication Scheme for a Replicated Database with Node Autonomy. VLDB 1994: 214-225
6. Yixiu Huang, A. Prasad Sistla, Ouri Wolfson: Data Replication for Mobile Computers. SIGMOD Conference 1994: 13-24
7. Yixiu Huang, Ouri Wolfson: Object Allocation in Distributed Databases and Mobile Computers. ICDE 1994: 20-29
8. Akhil Kumar, Arie Segev: Cost and Availability Tradeoffs in Replicated Data Concurrency Control. ACM Trans. Database Syst. 18(1): 102-131(1993)
9. John Rosenberg, Michael Hitchens: Linguistic Support for Persistent Modules and Capabilities. DBPL 1993: 32-49
10. Divyakant Agrawal, Amr El Abbadi: The Generalized Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. ACM Trans. Database Syst. 17(4): 689-717(1992)
11. 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)
12. Divyakant Agrawal, Amr El Abbadi: Resilient Logical Structures for Efficient Management of Replicated Data. VLDB 1992: 151-162
13. Sampath Rangarajan, Sanjeev Setia, Satish K. Tripathi: A Fault-Tolerant Algorithm for Replicated Data Management. ICDE 1992: 230-237
14. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
15. Donald B. Johnson, Larry Raab: A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols. PODS 1991: 75-81
16. Peter Triantafillou, David J. Taylor: Efficiently Maintaining Availability in the Presence of Partitionings in Distributed Systems. ICDE 1991: 34-41
17. Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
18. Divyakant Agrawal, Amr El Abbadi: The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. VLDB 1990: 243-254
19. Shun Yan Cheung, Mostafa H. Ammar, Mustaque Ahamad: The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. ICDE 1990: 438-445
20. Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989)
21. Shun Yan Cheung, Mustaque Ahamad, Mostafa H. Ammar: Optimizing Vote and Quorum Assignments for Reading and Writing Replicated Data. IEEE Trans. Knowl. Data Eng. 1(3): 387-397(1989)
22. Amr El Abbadi, Sam Toueg: The Group Paradigm for Concurrency Control Protocols. IEEE Trans. Knowl. Data Eng. 1(3): 376-386(1989)
23. Shun Yan Cheung, Mustaque Ahamad, Mostafa H. Ammar: Optimizing Vote and Quorum Assignments for Reading and Writing Replicated Data. ICDE 1989: 271-279
24. K. Brahmadathan, K. V. S. Ramarao: Read-Only Transactions in Partitioned Replicated Databases. ICDE 1989: 522-529
25. Junguk L. Kim: A Protocol for Consistent Surveillance of a Partitioned Network for Distributed Database Systems. DASFAA 1989: 259-265
26. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
27. Amr El Abbadi, Sam Toueg: The Group Paradigm for Concurrency Control Protocols. SIGMOD Conference 1988: 126-134
28. Ching-Liang Huang, Victor O. K. Li: A Quorum-Based Commit and Termination Protocol for Distributed Database Systems. ICDE 1988: 136-143
29. Akhil Kumar, Arie Segev: Optimizing Voting-Type Algorithms for Replicated Data. EDBT 1988: 428-442
30. Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987)
31. Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238
32. Amit P. Sheth, Anoop Singhal, Ming T. Liu: Performance Analysis of Resiliency Mechanisms in Distributed Datbase Systems. ICDE 1987: 419-428
33. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
34. Amr El Abbadi, Sam Toueg: Availability in Partitioned Replicated Databases. PODS 1986: 240-251
35. Calton Pu, Jerre D. Noe, Andrew Proudfoot: Regeneration of Replicated Objects: A Technique and Its Eden Implementation. ICDE 1986: 175-187
36. Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229
37. 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)
38. Dale Skeen, David D. Wright: Increasing Availability in Partitioned Database Systems. PODS 1984: 290-299