skip to main content
10.1145/1011767.1011803acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Signed quorum systems

Published:25 July 2004Publication History

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. D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. Resilient Overlay Networks. In Proceedings of the 18th Symposium on Operating Systems Principles (SOSP), October 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. D. Barbara and H. Garcia-Molina. The Reliability of Voting Mechanisms. IEEE Trans. Comput., pages 1197--1208, October 1987. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. R. Bazzi. Planar quorums. Theoretical Computer Science, 243:243--268, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. H. Garcia-Molina and D. Barbara. How to Assign Votes in a Distributed System. Journal of the ACM, October 1985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. D. K. Gifford. Weighted Voting for Replicated Data. In Proceedings of the 7th SOSP, 1979. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Y. Hassin and D. Peleg. Average probe complexity in quorum systems. In Proceedings of the ACM Symposium of Principles of Distributed Computing, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. R. Holzman, Y. Marcus, and D. Peleg. Load balancing in quorum systems. SIAM Journal on Discrete Mathematics, 10(2):223--245, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. D. Malkhi and M. Reiter. Byzantine Quorum Systems. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 569--578, May 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. D. Malkhi, M. Reiter, A. Wool, and R. Wright. Probabilistic Quorum Systems. The Information and Computation Journal, 170(2), November 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. M. Naor and U. Wieder. Scalable and Dynamic Quorum Systems. In Proceedings of the ACM Symposium of Principles of Distributed Computing, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. M. Naor and A. Wool. The Load, Capacity, and Availability of Quorum Systems. SIAM Journal on Computing, 27(2):423--447, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. D. Peleg and A. Wool. The Availability of Quorum Systems. Information and Computation, pages 210--223, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. D. Peleg and A. Wool. How to Be an Efficient Snoop, or the Probe Complexity of Quorum Systems. In Proceedings of the ACM Symposium of Principles of Distributed Computing, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan. Detour: A Case for Informed Internet Routing and Transport. IEEE Micro, 19(1), January 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. R. H. Thomas. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Transactions on Database Systems, 4:180--209, 1979. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  17. H. Yu. Overcoming the Majority Barrier in Large-Scale Systems. In Proceedings of the 17th International Symposium on Distributed Computing (DISC), October 2003.Google ScholarGoogle ScholarCross RefCross Ref
  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.Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. H. Yu and A. Vahdat. The Costs and Limits of Availability for Replicated Services. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP), October 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Signed quorum systems

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing
      July 2004
      422 pages
      ISBN:1581138024
      DOI:10.1145/1011767

      Copyright © 2004 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 25 July 2004

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • Article

      Acceptance Rates

      Overall Acceptance Rate740of2,477submissions,30%

      Upcoming Conference

      PODC '24

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader