A Locking Protocol for Resource Coordination in Distributed Databases.

@article{DBLP:journals/tods/MenascePM80,
  author    = {Daniel A. Menasc{\'e} and
               Gerald J. Popek and
               Richard R. Muntz},
  title     = {A Locking Protocol for Resource Coordination in Distributed Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {5},
  number    = {2},
  year      = {1980},
  pages     = {103-138},
  ee        = {http://doi.acm.org/10.1145/320141.320143, db/journals/tods/MenascePM80.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented. The proposed protocol is robust in the face of crashes of any participating site, as well as communication failures. Recovery from any number of failures during normal operation or any of the recovery stages is supported. Recovery is done in such a way that maximum forward progress is achieved by the recovery procedures. Integration of virtually any locking discipline including predicate lock methods is permitted by this protocol. The locking algorithm operates, and operates correctly, when the network is partitioned, either intentionally or by failure of communication lines. Each partition is able to continue with work local to it, and operation merges gracefully when the partitions are reconnected.

A subroutine of the protocol, that assures reliable communication among sites, is shown to have better performance than two-phase commit methods. For many topologies of interest, the delay introduced by the overall protocol is not a direct function of the size of the network. The communications cost is shown to grow in a relatively slow, linear fashion with the number of sites participating in the transaction. An informal proof of the correctness of the algorithm is also presented in this paper.

The algorithm has as its core a centralized locking protocol with distributed recovery procedures. A centralized controller with local appendages at each site coordinates all resource control, with requests initiated by application programs at any site. However, no site experiences undue load. Recovery is broken down into three disjoint mechanisms: for single node recovery, merge of partitions, and reconstruction of the centralized controller and tables. The disjointness of the mechanisms contributes to comprehensibility and ease of proof.

The paper concludes with a proposal for an extension aimed at optimizing operation of the algorithm to adapt to highly skewed distributions of activity. The extension applies nicely to interconnected computer networks.

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

Conference Abstract

References

[1]

...

[2]

...

[3]

...

[4]

...

[5]

Clarence A. Ellis: Consistency and Correctness of Duplicate Database Systems. SOSP 1977: 67-84 BibTeX

[6]

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

[7]

...

[8]

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

[9]

...

[10]

...

[11]

Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 BibTeX

[12]

...

[13]

...

Referenced by

1. Vadim V. Doubrovski: Key Integrity for Cooperative Database Environments with Stationary and Mobile Hosts. ADBIS 1996: 134-140
2. Amit P. Sheth, Anoop Singhal, Ming T. Liu: Performance Analysis of Resiliency Mechanisms in Distributed Datbase Systems. ICDE 1987: 419-428
3. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
   Contents
4. Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983)
5. Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983)
6. 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
7. Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper). VLDB 1982: 62-76
8. Eric C. Cooper: Analysis of Distributed Commit Protocols. SIGMOD Conference 1982: 175-183
9. Daniel A. Menascé, Tatuo Nakanishi: Performance Evaluation of a Two-Phase Commit Based Protocol for DDBS. PODS 1982: 247-255
10. Paris C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? PODS 1982: 98-107
11. Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
12. 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)
13. Daniel A. Menascé, Oscar E. Landes: On the Design of a Reliable Storage Component for Distributed Database Management Systems. VLDB 1980: 365-375