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

Dynamic Voting.

Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238
@inproceedings{DBLP:conf/sigmod/JajodiaM87,
  author    = {Sushil Jajodia and
               David Mutchler},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Dynamic Voting},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {227-238},
  ee        = {http://doi.acm.org/10.1145/38713.38740, db/conf/sigmod/JajodiaM87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In a voting-based algorithm, a replicated file can be updated in a partition if it contains a majority of copies. In this paper, we propose an extension of this scheme which permits a file to be updated in a partition provided it contains a majority of up-to-date copies. Our scheme not only preserves mutual consistency of the replicated file, but provides improvement in its availability as well. We develop a stochastic model which gives insight into the improvements afforded by our scheme over the voting scheme.

Copyright © 1987 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Umeshwar Dayal, Irving L. Traiger (Eds.): Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987. ACM Press 1987 BibTeX , SIGMOD Record 16(3)
Contents

Online Edition: ACM Digital Library

Journal Version

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

References

[1]
Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229 BibTeX
[2]
Amr El Abbadi, Sam Toueg: Availability in Partitioned Replicated Databases. PODS 1986: 240-251 BibTeX
[3]
...
[4]
Daniel Barbará, Hector Garcia-Molina, Annemarie Spauster: Protocols for Dynamic Vote Reassignment. PODC 1986: 195-205 BibTeX
[5]
...
[6]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[7]
Brian A. Coan, Brian M. Oki, Elliot K. Kolodner: Limitations on Database Availability when Networks Partition. PODC 1986: 187-194 BibTeX
[8]
Danco Davcev, Walter A. Burkhard: Consistency and Recovery Control for Replicated Files. SOSP 1985: 87-96 BibTeX
[9]
Susan B. Davidson: Optimism and Consistency In Partitioned Distributed Database Systems. ACM Trans. Database Syst. 9(3): 456-481(1984) BibTeX
[10]
Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) BibTeX
[11]
Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX
[12]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 BibTeX
[13]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[14]
Sushil Jajodia, Catherine Meadows: Mutual Consistency in Decentralized Distributed Systems. ICDE 1987: 396-404 BibTeX
[15]
Sushil Jajodia: Managing Replicated Files in Partitioned Distributed Database Systems. ICDE 1987: 412-418 BibTeX
[16]
Sushil Jajodia, David Mutchler: Enhancements to the Voting Algorithm. VLDB 1987: 399-406 BibTeX
[17]
Walter H. Kohler: A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems. ACM Comput. Surv. 13(2): 149-183(1981) BibTeX
[18]
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
[19]
...
[20]
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
[21]
Marshall C. Pease, Robert E. Shostak, Leslie Lamport: Reaching Agreement in the Presence of Faults. J. ACM 27(2): 228-234(1980) BibTeX
[22]
K. V. S. Ramarao: Detection of Mutual Inconsistency in Distributed Databases. ICDE 1987: 405-411 BibTeX
[23]
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
[24]
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
[25]
...
[26]
...
[27]
Dale Skeen, Michael Stonebraker: A Formal Model of Crash Recovery in a Distributed System. IEEE Trans. Software Eng. 9(3): 219-228(1983) BibTeX
[28]
Dale Skeen, David D. Wright: Increasing Availability in Partitioned Database Systems. PODS 1984: 290-299 BibTeX
[29]
...
[30]
David D. Wright: On Merging Partitioned Databases. SIGMOD Conference 1983: 6-14 BibTeX
[31]
...

Referenced by

  1. Xiangning Liu, Abdelsalam Helal, Weimin Du: Multiview Access Protocols for Large-Scale Replication. ACM Trans. Database Syst. 23(2): 158-198(1998)
  2. 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)
  3. Nabil R. Adam: A New Dynamic Voting Algorithm for Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 6(3): 470-478(1994)
  4. Peter Triantafillou, Feng Xiao: Supporting Partial Data Accesses to Replicated Data. ICDE 1994: 32-42
  5. Jian Tang, N. Natarajan: Obtaining Coteries That Optimize the Availability of Replicated Databases. IEEE Trans. Knowl. Data Eng. 5(2): 309-321(1993)
  6. Soon Myoung Chung: Enhanced Tree Quorum Algorithm for Replicated Distributed Databases. DASFAA 1993: 83-89
  7. Shun Yan Cheung, Mostafa H. Ammar, Mustaque Ahamad: The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. IEEE Trans. Knowl. Data Eng. 4(6): 582-592(1992)
  8. Sampath Rangarajan, Sanjeev Setia, Satish K. Tripathi: A Fault-Tolerant Algorithm for Replicated Data Management. ICDE 1992: 230-237
  9. Pankaj Jalote, Gagan Agrawal: Using Coding to Support Data Resiliency in Distributed Systems. ICDE 1992: 192-199
  10. Donald B. Johnson, Larry Raab: A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols. PODS 1991: 75-81
  11. Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
  12. Divyakant Agrawal, Amr El Abbadi: The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. VLDB 1990: 243-254
  13. Akhil Kumar: An Analysis of Borrowing Policies for Escrow Transactions in a Replicated Data Environment. ICDE 1990: 446-454
  14. Shun Yan Cheung, Mostafa H. Ammar, Mustaque Ahamad: The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. ICDE 1990: 438-445
  15. Sushil Jajodia, David Mutchler: A Hybrid Replica Control Algorithm Combining Static and Dynamic Voting. IEEE Trans. Knowl. Data Eng. 1(4): 459-469(1989)
  16. Shun Yan Cheung, Mustaque Ahamad, Mostafa H. Ammar: Optimizing Vote and Quorum Assignments for Reading and Writing Replicated Data. IEEE Trans. Knowl. Data Eng. 1(3): 387-397(1989)
  17. Jian Tang, N. Natarajan: A Static Pessimistic Scheme for Handling Replicated Databases. SIGMOD Conference 1989: 389-398
  18. Jian Tang, N. Natarajan: A Scheme for Maintaining Consistency and Availability of Replicated Files in a Partitioned Distributed System. ICDE 1989: 530-537
  19. Darrell D. E. Long, Jehan-François Pâris: Regeneration Protocols for Replicated Objects. ICDE 1989: 538-545
  20. Abdelsalam Helal, Jagannathan Srinivasan, Bharat K. Bhargava: SETH: A Quorum-Based Database System for Experimentation with Failures. ICDE 1989: 677-684
  21. Shun Yan Cheung, Mustaque Ahamad, Mostafa H. Ammar: Optimizing Vote and Quorum Assignments for Reading and Writing Replicated Data. ICDE 1989: 271-279
  22. Jehan-François Pâris, Darrell D. E. Long: Efficient Dynamic Voting Algorithms. ICDE 1988: 268-275
  23. Sushil Jajodia, David Mutchler: Integrating Static and Dynamic Voting Protocols To Enhance File Availability. ICDE 1988: 144-153
  24. Akhil Kumar, Arie Segev: Optimizing Voting-Type Algorithms for Replicated Data. EDBT 1988: 428-442
  25. Sushil Jajodia, David Mutchler: Enhancements to the Voting Algorithm. VLDB 1987: 399-406
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:39:49 2009