An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases.

@article{DBLP:journals/tods/BernsteinG84,
  author    = {Philip A. Bernstein and
               Nathan Goodman},
  title     = {An Algorithm for Concurrency Control and Recovery in Replicated
               Distributed Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {4},
  year      = {1984},
  pages     = {596-615},
  ee        = {http://doi.acm.org/10.1145/1994.2207, db/journals/tods/BernsteinG84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In a one-copy distributed database, each data item is stored at exactly one site. In a replicated database, some data items may be stored at multiple sites. The main motivation is improved reliability: by storing important data at multiple sites, the DBS can operate even though some sites have failed.

This paper describes an algorithm for handling replicated data, which allows users to operate on data so long as one copy is "available." A copy is "available" when (i) its site is up, and (ii) the copy is not out-of-date because of an earlier crash.

The algorithm handles clean, detectable site failures, but not Byzantine failures or network partitions.

Copyright © 1984 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]

...

[2]

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

[3]

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

[4]

Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper). VLDB 1982: 62-76 BibTeX

[5]

...

[6]

Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983) BibTeX

[7]

Philip A. Bernstein, Nathan Goodman, Vassos Hadzilacos: Recovery Algorithms for Database Systems. IFIP Congress 1983: 799-807 BibTeX

[8]

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

[9]

H. Breitwieser, M. Leszak: A Distributed Transaction Processing Protocol Based on Majority Consensus. PODC 1982: 224-237 BibTeX

[10]

Arvola Chan, Umeshwar Dayal, Stephen Fox, Nathan Goodman, Daniel R. Ries, Dale Skeen: Overview of an Ada Compatible Distributed Database Manager. SIGMOD Conference 1983: 228-237 BibTeX

[11]

Dean S. Daniels, Alfred Z. Spector: An Algorithm for Replicated Directories. PODC 1983: 104-113 BibTeX

[12]

Danny Dolev: The Byzantine Generals Strike Again. J. Algorithms 3(1): 14-30(1982) BibTeX

[13]

...

[14]

Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX

[15]

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

[16]

Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. PODS 1983: 1-7 BibTeX

[17]

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

[18]

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 BibTeX

[19]

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

[20]

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

[21]

Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms, Robert A. Yost: Computation and Communication in R*: A Distributed Database Manager. ACM Trans. Comput. Syst. 2(1): 24-38(1984) BibTeX

[22]

...

[23]

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

[24]

Marshall C. Pease, Robert E. Shostak, Leslie Lamport: Reaching Agreement in the Presence of Faults. J. ACM 27(2): 228-234(1980) BibTeX

[25]

David P. Reed: Implementing Atomic Actions on Decentralized Data. SOSP 1979: 163 BibTeX

[26]

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

[27]

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

[28]

Dale Skeen: Determining the Last Process to Fail. PODS 1983: 16-24 BibTeX

[29]

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

[30]

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

[31]

...

[32]

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

[33]

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

[34]

Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung: Locking Policies: Safety and Freedom from Deadlock. FOCS 1979: 286-297 BibTeX

Referenced by

1. Douglas B. Terry, Karin Petersen, Mike Spreitzer, Marvin Theimer: The Case for Non-transparent Replication: Examples from Bayou. IEEE Data Eng. Bull. 21(4): 12-20(1998)
2. Divyakant Agrawal, Amr El Abbadi: Using Reconfiguration for Efficient Management of Replicated Data. IEEE Trans. Knowl. Data Eng. 8(5): 786-801(1996)
3. Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi: Deferred Updates and Data Placement in Distributed Databases. ICDE 1996: 469-476
4. P. Krishna Reddy, Subhash Bhalla: A Nonblocking Transaction Data Flow Graph Based Protocol For Replicated Databases. IEEE Trans. Knowl. Data Eng. 7(5): 829-834(1995)
5. Salvatore T. March, Sangjyu Rho: Allocating Data and Operations to Nodes in Distributed Database Design. IEEE Trans. Knowl. Data Eng. 7(2): 305-317(1995)
6. 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
7. Nabil R. Adam: A New Dynamic Voting Algorithm for Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 6(3): 470-478(1994)
8. Akhil Kumar, Arie Segev: Cost and Availability Tradeoffs in Replicated Data Concurrency Control. ACM Trans. Database Syst. 18(1): 102-131(1993)
9. Yixiu Huang, Ouri Wolfson: A Competitive Dynamic Data Replication Algorithm. ICDE 1993: 310-317
10. Soon Myoung Chung: Enhanced Tree Quorum Algorithm for Replicated Distributed Databases. DASFAA 1993: 83-89
11. Pankaj Jalote, Gagan Agrawal: Using Coding to Support Data Resiliency in Distributed Systems. ICDE 1992: 192-199
12. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
13. Jehan-François Pâris, Darrell D. E. Long: Voting with Regenerable Volatile Witnesses. ICDE 1991: 112-119
14. Uwe M. Borghoff: Voting and Relocation Strategies Preserving Consistency among Replicated Files. ICDT 1990: 318-332
15. Shun Yan Cheung, Mostafa H. Ammar, Mustaque Ahamad: The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. ICDE 1990: 438-445
16. Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989)
17. Darrell D. E. Long, Jehan-François Pâris: Regeneration Protocols for Replicated Objects. ICDE 1989: 538-545
18. K. Brahmadathan, K. V. S. Ramarao: Read-Only Transactions in Partitioned Replicated Databases. ICDE 1989: 522-529
19. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
20. Akhil Kumar, Michael Stonebraker: Semantics Based Transaction Management Techniques for Replicated Data. SIGMOD Conference 1988: 117-125
21. Jehan-François Pâris: Efficient Management of Replicated Data. ICDT 1988: 396-409
22. Jehan-François Pâris, Darrell D. E. Long: Efficient Dynamic Voting Algorithms. ICDE 1988: 268-275
23. Bharat K. Bhargava, Paul Noll, Donna Sabo: An Experimental Analysis of Replicated Copy Control During Site Failure and Recovery. ICDE 1988: 82-91
24. Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987)
25. Dean S. Daniels, Alfred Z. Spector, Dean S. Thompson: Distributed Logging for Transaction Processing. SIGMOD Conference 1987: 82-96
26. Walter A. Burkhard, Bruce E. Martin, Jehan-François Pâris: The Gemini Replicated File System Test-bed. ICDE 1987: 441-448
27. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
28. Amr El Abbadi, Sam Toueg: Availability in Partitioned Replicated Databases. PODS 1986: 240-251
29. Calton Pu, Jerre D. Noe, Andrew Proudfoot: Regeneration of Replicated Objects: A Technique and Its Eden Implementation. ICDE 1986: 175-187