dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Quorum Systems in Replicated Databases: Science or Fiction?

Avishai Wool: Quorum Systems in Replicated Databases: Science or Fiction? IEEE Data Eng. Bull. 21(4): 3-11(1998)
@article{DBLP:journals/debu/Wool98,
  author    = {Avishai Wool},
  title     = {Quorum Systems in Replicated Databases: Science or Fiction?},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {21},
  number    = {4},
  year      = {1998},
  pages     = {3-11},
  ee        = {db/journals/debu/Wool98.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A quorum system is a collection of subsets of servers, every two of which intersect. Quorum systems have been suggested as a tool for concurrency control in replicated databases almost twenty years ago. They promised to guarantee strict consistency and to provide high availability and fault-tolerance in the face of server crashes and network partitions. Despite these promises, current commercial replicated databases typically do not use quorum systems. Instead they use mechanisms which guarantee much weaker consistency, if any. Moreover, the interest in quorum systems seems to be waning even in the database research community.

This paper attempts to explain why quorum systems have not fulfilled their old promises, and at the same time to argue why the current state of affairs may change. As technological advances bring new capabilities, and new applications bring new requirements, the time may have come to review the validity of some long standing criticisms of quorum systems.

Another theme of this paper is to argue that if quorum systems are to play a role in database research, it is not likely to be for their claimed fault-tolerance capabilities. Rather, more attention should be given to a somewhat overlooked feature of quorum systems: they allow load balancing among servers while maintaining strict consistency. Thus quorum systems may offer a way to scale up the throughput of heavily loaded servers.

Copyright © 1998 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

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

Online Edition:

Data Engineering Bulletin December 1998: Data Replication (Divyakant Agrawal and Amr El Abbadi, eds.)
( letter+figures, letter-figures, A4+figures , A4-figures, PDF+figures)

References

[ABKW98]
Todd A. Anderson, Yuri Breitbart, Henry F. Korth, Avishai Wool: Replication, Consistency, and Practicality: Are These Mutually Exclusive? SIGMOD Conference 1998: 484-495 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ADKM92]
Yair Amir, Danny Dolev, Shlomo Kramer, Dalia Malki: Transis: A Communication Subsystem for High Availability. FTCS 1992: 76-84 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AE91]
Divyakant Agrawal, Amr El Abbadi: An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion. ACM Trans. Comput. Syst. 9(1): 1-20(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AMM+95]
Yair Amir, Louise E. Moser, P. M. Melliar-Smith, Deborah A. Agarwal, P. Ciarfella: The Totem Single-Ring Ordering and Membership Protocol. ACM Trans. Comput. Syst. 13(4): 311-342(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AW96]
Yair Amir, Avishai Wool: Evaluating Quorum Systems over the Internet. FTCS 1996: 26-35 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AW98]
Yair Amir, Avishai Wool: Optimal Availability Quorum Systems: Theory and Practice. Inf. Process. Lett. 65(5): 223-228(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Baz96]
Rida A. Bazzi: Planar Quorums. WDAG 1996: 251-268 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BG86]
Daniel Barbará, Hector Garcia-Molina: The Vulnerabilty of Vote Assignments. ACM Trans. Comput. Syst. 4(3): 187-213(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BG87]
Daniel Barbará, Hector Garcia-Molina: The Reliability of Voting Mechanisms. IEEE Trans. Computers 36(10): 1197-1208(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bir98]
...
[BK97]
Yuri Breitbart, Henry F. Korth: Replication and Consistency: Being Lazy Helps Sometimes. PODS 1997: 173-184 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BvR94]
...
[CL98]
...
[CRR96]
Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi: Deferred Updates and Data Placement in Distributed Databases. ICDE 1996: 469-476 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DGS85]
Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ET89]
Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GB85]
Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GHOS96]
Jim Gray, Pat Helland, Patrick E. O'Neil, Dennis Shasha: The Dangers of Replication and a Solution. SIGMOD Conference 1996: 173-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gif79]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GR93]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS92]
Hector Garcia-Molina, Kenneth Salem: Main Memory Database Systems: An Overview. IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Her86]
Maurice Herlihy: A Quorum-Consensus Replication Method for Abstract Data Types. ACM Trans. Comput. Syst. 4(1): 32-53(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HHB96]
...
[INK95]
Toshihide Ibaraki, Hiroshi Nagamochi, Tsunehiko Kameda: Optimal Coteries for Rings and Related Networks. Distributed Computing 8(4): 191-201(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JLR+94]
H. V. Jagadish, Daniel F. Lieuwen, Rajeev Rastogi, Abraham Silberschatz, S. Sudarshan: Dalí: A High Performance Main Memory Storage Manager. VLDB 1994: 48-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KC91]
Akhil Kumar, Shun Yan Cheung: A High Availability \sqrt{N} Hierarchical Grid Algorithm for Replicated Data. Inf. Process. Lett. 40(6): 311-316(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kum91]
Akhil Kumar: Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data. IEEE Trans. Computers 40(9): 996-1004(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lyn96]
...
[Mae85]
Mamoru Maekawa: A Square Root N Algorithm for Mutual Exclusion in Decentralized Systems. ACM Trans. Comput. Syst. 3(2): 145-159(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MR98a]
Dahlia Malkhi, Michael K. Reiter: Byzantine Quorum Systems. Distributed Computing 11(4): 203-213(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MR98b]
...
[MRW97]
Dahlia Malkhi, Michael K. Reiter, Avishai Wool: The Load and Availability of Byzantine Quorum Systems. PODC 1997: 249-257 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NW98]
Moni Naor, Avishai Wool: The Load, Capacity, and Availability of Quorum Systems. SIAM J. Comput. 27(2): 423-447(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ora97]
...
[PW95]
...
[PW97a]
...
[PW97b]
David Peleg, Avishai Wool: Crumbling Walls: A Class of Practical and Efficient Quorum Systems. Distributed Computing 10(2): 87-97(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RDB98]
...
[RST92]
Sampath Rangarajan, Sanjeev Setia, Satish K. Tripathi: A Fault-Tolerant Algorithm for Replicated Data Management. ICDE 1992: 230-237 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SB94]
...
[Tho79]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VMS]
...
[vRBM96]
Robbert van Renesse, Kenneth P. Birman, Silvano Maffeis: Horus: A Flexible Group Communication System. Commun. ACM 39(4): 76-83(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 17:54:41 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page