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

Referenced by

  1. Ouri Wolfson, Sushil Jajodia, Yixiu Huang: An Adaptive Data Replication Algorithm. ACM Trans. Database Syst. 22(2): 255-314(1997)
  2. Divyakant Agrawal, Amr El Abbadi: Using Reconfiguration for Efficient Management of Replicated Data. IEEE Trans. Knowl. Data Eng. 8(5): 786-801(1996)
  3. P. Krishna Reddy, Subhash Bhalla: A Nonblocking Transaction Data Flow Graph Based Protocol For Replicated Databases. IEEE Trans. Knowl. Data Eng. 7(5): 829-834(1995)
  4. Chang S. Keum, Wan Choi, Eui Kyeong Hong, Won-Young Kim, Kyu-Young Whang: Performance Evaluation of Replica Control Algorithms in a Locally Distributed Database System. DASFAA 1995: 388-396
  5. Kenneth J. Goldman, Nancy A. Lynch: Quorum Consensus in Nested Transaction Systems. ACM Trans. Database Syst. 19(4): 537-585(1994)
  6. Ravi Mukkamala: Storage Efficient and Secure Replicated Distribted Databases. IEEE Trans. Knowl. Data Eng. 6(2): 337-341(1994)
  7. Nabil R. Adam: A New Dynamic Voting Algorithm for Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 6(3): 470-478(1994)
  8. Peter Triantafillou, Feng Xiao: Supporting Partial Data Accesses to Replicated Data. ICDE 1994: 32-42
  9. Michael Rabinovich, Edward D. Lazowska: Efficient Support for Partial Write Operations in Replicated Databases. ICDE 1994: 43-53
  10. Akhil Kumar, Arie Segev: Cost and Availability Tradeoffs in Replicated Data Concurrency Control. ACM Trans. Database Syst. 18(1): 102-131(1993)
  11. Divyakant Agrawal, Amr El Abbadi: The Generalized Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. ACM Trans. Database Syst. 17(4): 689-717(1992)
  12. Divyakant Agrawal, Amr El Abbadi: Resilient Logical Structures for Efficient Management of Replicated Data. VLDB 1992: 151-162
  13. Michael Rabinovich, Edward D. Lazowska: Improving Fault Tolerance and Supporting Partial Writes in Structured Coterie Protocols for Replicated Objects. SIGMOD Conference 1992: 226-235
  14. Michael Rabinovich, Edward D. Lazowska: A Fault-Tolerant Commit Protocol for Replicated Databases. PODS 1992: 139-148
  15. P. C. Aristides, Amr El Abbadi: Fast Read-Only Transactions in Replicated Databases. ICDE 1992: 246-253
  16. Donald B. Johnson, Larry Raab: A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols. PODS 1991: 75-81
  17. Sushil Jajodia, David Mutchler: A Hybrid Replica Control Algorithm Combining Static and Dynamic Voting. IEEE Trans. Knowl. Data Eng. 1(4): 459-469(1989)
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 18:39:08 2008