Quorum Systems in Replicated Databases: Science or Fiction?

@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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition:

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 BibTeX

[ADKM92]

Yair Amir, Danny Dolev, Shlomo Kramer, Dalia Malki: Transis: A Communication Subsystem for High Availability. FTCS 1992: 76-84 BibTeX

[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) BibTeX

[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) BibTeX

[AW96]

Yair Amir, Avishai Wool: Evaluating Quorum Systems over the Internet. FTCS 1996: 26-35 BibTeX

[AW98]

Yair Amir, Avishai Wool: Optimal Availability Quorum Systems: Theory and Practice. Inf. Process. Lett. 65(5): 223-228(1998) BibTeX

[Baz96]

Rida A. Bazzi: Planar Quorums. WDAG 1996: 251-268 BibTeX

[BG86]

Daniel Barbará, Hector Garcia-Molina: The Vulnerabilty of Vote Assignments. ACM Trans. Comput. Syst. 4(3): 187-213(1986) BibTeX

[BG87]

Daniel Barbará, Hector Garcia-Molina: The Reliability of Voting Mechanisms. IEEE Trans. Computers 36(10): 1197-1208(1987) BibTeX

[Bir98]

...

[BK97]

Yuri Breitbart, Henry F. Korth: Replication and Consistency: Being Lazy Helps Sometimes. PODS 1997: 173-184 BibTeX

[BvR94]

...

[CL98]

...

[CRR96]

Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi: Deferred Updates and Data Placement in Distributed Databases. ICDE 1996: 469-476 BibTeX

[DGS85]

Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) BibTeX

[ET89]

Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989) BibTeX

[GB85]

Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985) BibTeX

[GHOS96]

Jim Gray, Pat Helland, Patrick E. O'Neil, Dennis Shasha: The Dangers of Replication and a Solution. SIGMOD Conference 1996: 173-182 BibTeX

[Gif79]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[GR93]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX

[GS92]

Hector Garcia-Molina, Kenneth Salem: Main Memory Database Systems: An Overview. IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992) BibTeX

[Her86]

Maurice Herlihy: A Quorum-Consensus Replication Method for Abstract Data Types. ACM Trans. Comput. Syst. 4(1): 32-53(1986) BibTeX

[HHB96]

...

[INK95]

Toshihide Ibaraki, Hiroshi Nagamochi, Tsunehiko Kameda: Optimal Coteries for Rings and Related Networks. Distributed Computing 8(4): 191-201(1995) BibTeX

[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 BibTeX

[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) BibTeX

[Kum91]

Akhil Kumar: Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data. IEEE Trans. Computers 40(9): 996-1004(1991) BibTeX

[Lyn96]

...

[Mae85]

Mamoru Maekawa: A Square Root N Algorithm for Mutual Exclusion in Decentralized Systems. ACM Trans. Comput. Syst. 3(2): 145-159(1985) BibTeX

[MR98a]

Dahlia Malkhi, Michael K. Reiter: Byzantine Quorum Systems. Distributed Computing 11(4): 203-213(1998) BibTeX

[MR98b]

...

[MRW97]

Dahlia Malkhi, Michael K. Reiter, Avishai Wool: The Load and Availability of Byzantine Quorum Systems. PODC 1997: 249-257 BibTeX

[NW98]

Moni Naor, Avishai Wool: The Load, Capacity, and Availability of Quorum Systems. SIAM J. Comput. 27(2): 423-447(1998) BibTeX

[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) BibTeX

[RDB98]

...

[RST92]

Sampath Rangarajan, Sanjeev Setia, Satish K. Tripathi: A Fault-Tolerant Algorithm for Replicated Data Management. ICDE 1992: 230-237 BibTeX

[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) BibTeX

[VMS]

...

[vRBM96]

Robbert van Renesse, Kenneth P. Birman, Silvano Maffeis: Horus: A Flexible Group Communication System. Commun. ACM 39(4): 76-83(1996) BibTeX