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