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

A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols.

Donald B. Johnson, Larry Raab: A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols. PODS 1991: 75-81
@inproceedings{DBLP:conf/pods/JohnsonR91,
  author    = {Donald B. Johnson and
               Larry Raab},
  title     = {A Tight Upper Bound on the Benefits of Replication and Consistency
               Control Protocols},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {75-81},
  ee        = {http://doi.acm.org/10.1145/113413.113420, db/conf/pods/JohnsonR91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present an upper bound on the performance provided by a protocol guaranteeing mutually exclusive access to a replicated resource in a network subject to component failure and subsequent partitioning. The bound is presented in terms of the performance of a single resource in the same network. The bound is tight and is the first such bound known to us. Since mutual exclusion is one of the requirements for maintaining the consistency of a database object, this bound provides an upper limit on the availability provided by any database consistency control protocol, including those employing dynamic data relocation and replication. We show that if a single copy provides availability A for 0 <= A <= 1, then no scheme can achieve availabdity greater than sqrt(A) in the same network. We show this bound to be the best possible for any network with availabdity greater than .25. Although, as we prove, the problem of calculating A is #P-completet, we describe a method for approximating the optimal location for a single copy which adjusts dynamically to current network characteristics. This bound is most useful for high availabilities, which tend to be obtainable with modern networks and their constituent sites and links.

Copyright © 1991 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 Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 693 KB]

References

[1]
...
[2]
...
[3]
...
[4]
Daniel Barbará, Hector Garcia-Molina, Annemarie Spauster: Increasing Availability Under Mutual Exclusion Constraints with Dynamic Vote Reassignment. ACM Trans. Comput. Syst. 7(4): 394-426(1989) BibTeX
[5]
...
[6]
...
[7]
Danco Davcev, Walter A. Burkhard: Consistency and Recovery Control for Replicated Files. SOSP 1985: 87-96 BibTeX
[8]
Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX
[9]
Amr El Abbadi, Sam Toueg: Availability in Partitioned Replicated Databases. PODS 1986: 240-251 BibTeX
[10]
...
[11]
Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985) BibTeX
[12]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[13]
...
[14]
...
[15]
Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238 BibTeX
[16]
Sushil Jajodia, David Mutchler: Enhancements to the Voting Algorithm. VLDB 1987: 399-406 BibTeX
[17]
Sushil Jajodia, David Mutchler: Integrating Static and Dynamic Voting Protocols To Enhance File Availability. ICDE 1988: 144-153 BibTeX
[18]
Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990) BibTeX
[19]
...
[20]
...
[21]
...
[22]
Jehan-François Pâris, Darrell D. E. Long: Efficient Dynamic Voting Algorithms. ICDE 1988: 268-275 BibTeX
[23]
Appajosyula Satyanarayana, R. Kevin Wood: A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks. SIAM J. Comput. 14(4): 818-832(1985) BibTeX
[24]
Dale Skeen, David D. Wright: Increasing Availability in Partitioned Database Systems. PODS 1984: 290-299 BibTeX
[25]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX
[26]
Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421(1979) BibTeX

Referenced by

  1. Peter Triantafillou, David J. Taylor: VELOS: A New Approach for Efficiently Achieving High Availability in Partitioned Distributed Systems. IEEE Trans. Knowl. Data Eng. 8(2): 305-321(1996)
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:34:02 2009