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.
- 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 ScholarDigital Library
- D. Barbara and H. Garcia-Molina. The Reliability of Voting Mechanisms. IEEE Trans. Comput., pages 1197--1208, October 1987. Google ScholarDigital Library
- R. Bazzi. Planar quorums. Theoretical Computer Science, 243:243--268, 2000. Google ScholarDigital Library
- H. Garcia-Molina and D. Barbara. How to Assign Votes in a Distributed System. Journal of the ACM, October 1985. Google ScholarDigital Library
- D. K. Gifford. Weighted Voting for Replicated Data. In Proceedings of the 7th SOSP, 1979. Google ScholarDigital Library
- Y. Hassin and D. Peleg. Average probe complexity in quorum systems. In Proceedings of the ACM Symposium of Principles of Distributed Computing, 2001. Google ScholarDigital Library
- R. Holzman, Y. Marcus, and D. Peleg. Load balancing in quorum systems. SIAM Journal on Discrete Mathematics, 10(2):223--245, 1997. Google ScholarDigital Library
- 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 ScholarDigital Library
- D. Malkhi, M. Reiter, A. Wool, and R. Wright. Probabilistic Quorum Systems. The Information and Computation Journal, 170(2), November 2001. Google ScholarDigital Library
- M. Naor and U. Wieder. Scalable and Dynamic Quorum Systems. In Proceedings of the ACM Symposium of Principles of Distributed Computing, 2003. Google ScholarDigital Library
- M. Naor and A. Wool. The Load, Capacity, and Availability of Quorum Systems. SIAM Journal on Computing, 27(2):423--447, 1998. Google ScholarDigital Library
- D. Peleg and A. Wool. The Availability of Quorum Systems. Information and Computation, pages 210--223, 1995. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- R. H. Thomas. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Transactions on Database Systems, 4:180--209, 1979. Google ScholarDigital Library
- 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 Scholar
- H. Yu. Overcoming the Majority Barrier in Large-Scale Systems. In Proceedings of the 17th International Symposium on Distributed Computing (DISC), October 2003.Google ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
Signed quorum systems
Recommendations
Read-Write Quorum Systems Made Practical
PaPoC '21: Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed DataQuorum systems are a powerful mechanism for ensuring the consistency of replicated data. Production systems usually opt for majority quorums due to their simplicity and fault tolerance, but majority quorum systems provide poor throughput and ...
Signed quorum systems
AbstractWith 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 ...
The Load and Availability of Byzantine Quorum Systems
Replicated services accessed via quorums enable each access to be performed at only a subset (quorum) of the servers and achieve consistency across accesses by requiring any two quorums to intersect. Recently, b-masking quorum systems, whose ...
Comments