ACM SIGMOD Anthology TODS dblp.uni-trier.de

Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database.

Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
@article{DBLP:journals/tods/JajodiaM90,
  author    = {Sushil Jajodia and
               David Mutchler},
  title     = {Dynamic Voting Algorithms for Maintaining the Consistency of
               a Replicated Database},
  journal   = {ACM Trans. Database Syst.},
  volume    = {15},
  number    = {2},
  year      = {1990},
  pages     = {230-280},
  ee        = {http://doi.acm.org/10.1145/78922.78926, db/journals/tods/JajodiaM90.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

There are several replica control algorithms for managing replicated files in the face of network partitioning due to site or communication link failures. Pessimistic algorithms ensure consistency at the price of reduced availability; they permit at most one (distinguished) partition to process updates at any given time. The best known pessimistic algorithm, voting, is a "static" algorithm, meaning that all potential distinguished partitions can be listed in advance. We present a dynamic extension of voting called dynamic voting. This algorithm permits updates in a partition provided it contains more than half of the up-to-date copies of the replicated file. We also present an extension of dynamic voting called dynamic voting with linearly ordered copies (abbreviated as dynamic-linear). These algorithms are dynamic because the order in which past distinguished partitions were created plays a role in the selection of the next distinguished partition. Our algorithms have all the virtues of ordinary voting, including its simplicity, and provide improved availability as well. We provide two stochastic models to support the latter claim. In the first (site) model, sites may fail but communication links are infallible; in the second (link) model the reverse is true. We prove that under the site model, dynamic-linear has greater availability than any static algorithm, including weighted voting, if there are four or more sites in the network. In the link model, we consider all biconnected five-site networks and a wide variety of failure and repair rates. In all cases considered, dynamic-linear had greater availability than any static algorithm.

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

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Versions

References

[1]
Mustaque Ahamad, Mostafa H. Ammar: Performance Characterization of Quorum-Consensus Algorithms for Replicated Data. IEEE Trans. Software Eng. 15(4): 492-501(1989) BibTeX
[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]
Daniel Barbará, Hector Garcia-Molina: The Reliability of Voting Mechanisms. IEEE Trans. Computers 36(10): 1197-1208(1987) BibTeX
[5]
Daniel Barbará, Hector Garcia-Molina: The Vulnerabilty of Vote Assignments. ACM Trans. Comput. Syst. 4(3): 187-213(1986) BibTeX
[6]
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
[7]
Daniel Barbará, Hector Garcia-Molina, Annemarie Spauster: Policies for Dynamic Vote Reassignment. ICDCS 1986: 37-44 BibTeX
[8]
Daniel Barbará, Hector Garcia-Molina, Annemarie Spauster: Protocols for Dynamic Vote Reassignment. PODC 1986: 195-205 BibTeX
[9]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[10]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[11]
Barbara T. Blaustein, Charles W. Kaufman: Updating Replicated Data During Communications Failures. VLDB 1985: 49-58 BibTeX
[12]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[13]
Bruce W. Char, Gregory J. Fee, Keith O. Geddes, Gaston H. Gonnet, Michael B. Monagan: A Tutorial Introduction to Maple. J. Symb. Comput. 2(2): 179-200(1986) BibTeX
[14]
Eric C. Cooper: Analysis of Distributed Commit Protocols. SIGMOD Conference 1982: 175-183 BibTeX
[15]
Danco Davcev, Walter A. Burkhard: Consistency and Recovery Control for Replicated Files. SOSP 1985: 87-96 BibTeX
[16]
Susan B. Davidson: Optimism and Consistency In Partitioned Distributed Database Systems. ACM Trans. Database Syst. 9(3): 456-481(1984) BibTeX
[17]
Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) BibTeX
[18]
Joanne Bechta Dugan, Gianfranco Ciardo: Stochastic Petri Net Analysis of a Replicated File System. IEEE Trans. Software Eng. 15(4): 394-401(1989) BibTeX
[19]
Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX
[20]
Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229 BibTeX
[21]
Amr El Abbadi, Sam Toueg: Availability in Partitioned Replicated Databases. PODS 1986: 240-251 BibTeX
[22]
Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989) BibTeX
[23]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 BibTeX
[24]
Hector Garcia-Molina: Elections in a Distributed Computing System. IEEE Trans. Computers 31(1): 48-59(1982) BibTeX
[25]
...
[26]
Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985) BibTeX
[27]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[28]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[29]
Sushil Jajodia, Catherine Meadows: Mutual Consistency in Decentralized Distributed Systems. ICDE 1987: 396-404 BibTeX
[30]
Sushil Jajodia, David Mutchler: A Pessimistic Consistency Control Algorithm for Replicated Files which Achieves High Availability. IEEE Trans. Software Eng. 15(1): 39-46(1989) BibTeX
[31]
Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238 BibTeX
[32]
Sushil Jajodia, David Mutchler: Enhancements to the Voting Algorithm. VLDB 1987: 399-406 BibTeX
[33]
Sushil Jajodia, David Mutchler: Integrating Static and Dynamic Voting Protocols To Enhance File Availability. ICDE 1988: 144-153 BibTeX
[34]
Walter H. Kohler: A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems. ACM Comput. Surv. 13(2): 149-183(1981) BibTeX
[35]
...
[36]
...
[37]
Toshimi Minoura, Gio Wiederhold: Resilient Extended True-Copy Token Scheme for a Distributed Database System. IEEE Trans. Software Eng. 8(3): 173-189(1982) BibTeX
[38]
...
[39]
Jehan-François Pâris: Voting with Witnesses: A Constistency Scheme for Replicated Files. ICDCS 1986: 606-612 BibTeX
[40]
Douglas Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David A. Edwards, Stephen Kiser, Charles S. Kline: Detection of Mutual Inconsistency in Distributed Systems. IEEE Trans. Software Eng. 9(3): 240-247(1983) BibTeX
[41]
Marshall C. Pease, Robert E. Shostak, Leslie Lamport: Reaching Agreement in the Presence of Faults. J. ACM 27(2): 228-234(1980) BibTeX
[42]
K. V. S. Ramarao: Detection of Mutual Inconsistency in Distributed Databases. ICDE 1987: 405-411 BibTeX
[43]
K. V. S. Ramarao: Transaction Atomicity in the Presence of Network Partitions. ICDE 1988: 512-519 BibTeX
[44]
Sunil K. Sarin, Barbara T. Blaustein, Charles W. Kaufman: System Architecture for Partition-Tolerant Distributed Databases. IEEE Trans. Computers 34(12): 1158-1163(1985) BibTeX
[45]
Richard D. Schlichting, Fred B. Schneider: Fail-Stop Processors: An Approach to Designing Fault-Tolerant Computing Systems. ACM Trans. Comput. Syst. 1(3): 222-238(1983) BibTeX
[46]
...
[47]
...
[48]
Dale Skeen, Michael Stonebraker: A Formal Model of Crash Recovery in a Distributed System. IEEE Trans. Software Eng. 9(3): 219-228(1983) BibTeX
[49]
Dale Skeen, David D. Wright: Increasing Availability in Partitioned Database Systems. PODS 1984: 290-299 BibTeX
[50]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX
[51]
...
[52]
...
[53]
...
[54]
David D. Wright: On Merging Partitioned Databases. SIGMOD Conference 1983: 6-14 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 20:11:50 2008