|
|
|
@inproceedings{DBLP:conf/sigmod/MenascePM78,
author = {Daniel A. Menasc{\'e} and
Gerald J. Popek and
Richard R. Muntz},
editor = {Eugene I. Lowenthal and
Nell B. Dale},
title = {A Locking Protocol for Resource Coordination in Distributed Databases
(Abstract)},
booktitle = {Proceedings of the 1978 ACM SIGMOD International Conference on
Management of Data, Austin, Texas, May 31 - June 2, 1978},
publisher = {ACM},
year = {1978},
pages = {2},
ee = {http://doi.acm.org/10.1145/509252.509256, db/conf/sigmod/MenascePM78.html},
crossref = {DBLP:conf/sigmod/78},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented in this paper. 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. 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.
It is shown in this paper that for many topologies of interest, the delay introduced by the protocol is not a direct function of the size of the network. The communication cost is shown to grow in a relatively slow, linear fashion with the number of sites in the network. 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. Recovery is broken down into three disjoint mechanisms; for single node recovery, merge of partitions and reconstruction of the centralized controller and tables.
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 © 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.
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...