Signed quorum systems

ABSTRACT

With n servers that independently fail with probability of p < 0.5, it is well known that the majority quorum system achieves the best availability among all quorum systems. However, even this optimal construction requires (n+1)/2 functioning servers out of n. Furthermore, the number of probes needed to acquire a quorum is also lower bounded by (n+1)/2.Motivated by the need for a highly available and low probe complexity quorum system in the Internet, this paper proposes signed quorum systems (SQS) that can be available as long as any O(1) servers are available, and simultaneously have O(1) probe complexity. SQS provides probabilistic intersection guarantees and exploits the property of independent mismatches in today's Internet. Such key property has been validated previously under multiple Internet measurement traces. This paper then extensively studies the availability, probe complexity, and load of SQS, derives lower bounds for all three metrics, and constructs matching upper bounds. We show that in addition to the qualitatively superior availability and probe complexity, SQS also decouples availability from load and probe complexity, so that optimal availability can be achieved under most probe complexity and load values.

REFERENCES

• 1: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: D. Barbara , H. Garcia-Molina, The reliability of voting mechanisms, IEEE Transactions on Computers, v.36 n.10, p.1197-1208, Oct. 1987 [doi>10.1109/TC.1987.1676860]
• 3: Rida A. Bazzi, Planar quorums, Theoretical Computer Science, v.243 n.1-2, p.243-268, July 28, 2000 [doi>10.1016/S0304-3975(98)00208-4]
• 4: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• 5: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 6: Yehuda Hassin , David Peleg, Average probe complexity in quorum systems, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.180-189, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384014]
• 7: Ron Holzman , Yosi Marcus , David Peleg, Load Balancing in Quorum Systems, SIAM Journal on Discrete Mathematics, v.10 n.2, p.223-245, May 1997 [doi>10.1137/S0895480193260303]
• 8: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.569-578, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258650]
• 9: Dahlia Malkhi , Michael K. Reiter , Avishai Wool , Rebecca N. Wright, Probabilistic quorum systems, Information and Computation, v.170 n.2, p.184-206, November 1, 2001 [doi>10.1006/inco.2001.3054]
• 10: Moni Naor , Udi Wieder, Scalable and dynamic quorum systems, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.114-122, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872052]
• 11: Moni Naor , Avishai Wool, The Load, Capacity, and Availability of Quorum Systems, SIAM Journal on Computing, v.27 n.2, p.423-447, April 1998 [doi>10.1137/S0097539795281232]
• 12: David Peleg , Avishai Wool, The availability of quorum systems, Information and Computation, v.123 n.2, p.210-223, Dec. 1995 [doi>10.1006/inco.1995.1169]
• 13: David Peleg , Avishai Wool, How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.290-299, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248112]
• 14: Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
• 15: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 16: A. Yao. Probabilistic Computations: Towards a Unified Measure of Complexity. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pages 222--227, 1977.
• 17: H. Yu. Overcoming the Majority Barrier in Large-Scale Systems. In Proceedings of the 17th International Symposium on Distributed Computing (DISC), October 2003.
• 18: H. Yu. Signed Quorum Systems. Technical Report IRP-TR-04-04, Intel Research Pittsburgh, 2004. Also available at http://www.cs.cmu.edu/~yhf.
• 19: Haifeng Yu , Amin Vahdat, The costs and limits of availability for replicated services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
availability, load, probe complexity, quorum systems, tradeoff