ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Optimal Termination Prococols for Network Partitioning.

Francis Y. L. Chin, K. V. S. Ramarao: Optimal Termination Prococols for Network Partitioning. PODS 1983: 25-35
@inproceedings{DBLP:conf/pods/ChinR83,
  author    = {Francis Y. L. Chin and
               K. V. S. Ramarao},
  title     = {Optimal Termination Prococols for Network Partitioning},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {25-35},
  ee        = {http://doi.acm.org/10.1145/588058.588064, db/conf/pods/ChinR83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Commit protocols guarantee the consistency of distributed databases in absence of any failures. A commit protocol is resilient to a class of failures if it is possible to guarantee that a) databases at all operational sites in presence of these failures are consistent and b) other sites can be recovered consistently with these sites when the failure is repaired. Such a commit protocol is called nonblocking if no operational site needs to wait on a transaction which is incomplete at the time of the failure. It is known that no nonblocking commit protocol resilient to network partitioning exists. In this paper, the possible termination protocols of commit protocols are studied in the context of network partitioning. A formal model for termination protocols is introduced and a general logical interpretation of termination protocols is presented. The model makes use of all the information that is available in a component of the partition - namely, the constituent sites and their respective states at the time of partition. Optimality measures for the termination protocols in terms of the number of waiting components and average number of waiting sites are introduced and protocols optimal under these measures are produced for all the possible centralized and decentralized commit protocols. It is proved that quorum-based termination protocols indeed perform very well in the presence of network partitioning. If the central site(s) is reliable, we can prove that centralized commit protocols indeed perform better than all decentralized ones. Thus, the general preference for centralized commit protocols is justified.

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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library

References

[Alsb]
...
[Brei]
H. Breitwieser, M. Leszak: A Distributed Transaction Processing Protocol Based on Majority Consensus. PODC 1982: 224-237 BibTeX
[Coop]
Eric C. Cooper: Analysis of Distributed Commit Protocols. SIGMOD Conference 1982: 175-183 BibTeX
[Dole1]
Danny Dolev, H. Raymond Strong: Requirements for Agreement in a Distributed System. DDB 1982: 115-129 BibTeX
[Dole2]
Danny Dolev, H. Raymond Strong: Polynomial Algorithms for Multiple Processor Agreement. STOC 1982: 401-407 BibTeX
[Dole3]
...
[Dole4]
...
[Gray]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Hamm]
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
[Lamp]
...
[Skee]
...
[Skee1]
Dale Skeen, Michael Stonebraker: A Formal Model of Crash Recovery in a Distributed System. Berkeley Workshop 1981: 129-142 BibTeX
[Skee2]
Dale Skeen: Nonblocking Commit Protocols. SIGMOD Conference 1981: 133-142 BibTeX
[Skee3]
...
[Scha]
...

Referenced by

  1. Idit Keidar, Danny Dolev: Increasing the Resilience of Atomic Commit at No Additional Cost. PODS 1995: 245-254
  2. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:41 2009