×

Probabilistic quorum systems. (English) Zbl 1005.68017

Summary: We initiate the study of probabilistic quorum systems, a technique for providing consistency of replicated data with high levels of assurance despite the failure of data servers. We show that this technique offers effective load reduction on servers and high availability. We explore probabilistic quorum systems both for services tolerant of benign server failures and for services tolerant of arbitrary (Byzantine) ones. We also prove bounds on the server load that can be achieved with these techniques.

MSC:

68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrawal, D.; El Abbadi, A., An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Trans. Comput. Systems, 9, 1-20 (1991)
[2] Agrawal, D.; El-Abbadi, A.; Steinke, R., Epidemic algorithms in replicated databases, Proc. 16th ACM SIGACT-SIGMOD Symp. Princip. of Database Systems (PODS) (1997)
[3] Aumann, Y.; Rabin, M., Clock construction in fully asynchronous parallel systems and PRAM simulation, Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (1992), p. 147-156 · Zbl 0977.68877
[4] Barbara, D.; Garcia-Molina, H., The vulnerability of vote assignments, ACM Trans. Comput. Systems, 4, 187-213 (1986)
[5] Barbara, D.; Garcia-Molina, H., The reliability of vote mechanisms, IEEE Trans. Comput., 36, 1197-1208 (1987)
[6] Bernstein, P. A.; Hadzilacos, V.; Goodman, N., Concurrency Control and Recovery in Database Systems (1987), Addison-Wesley: Addison-Wesley Reading
[7] Bazzi, R., Planar quorums, Proceedings of the 10th International Workshop on Distributed Algorithms (WDAG) (1996), Bologna, p. 251-568 · Zbl 0944.68004
[8] Bazzi, R. A., Synchronous Byzantine quorum systems, Proceedings of the 16th ACM Symposium on Principles of Distributed Computing (1997), p. 259-266 · Zbl 1373.68132
[9] Bazzi, R., Nonblocking asynchronous Byzantine quorum systems, Proceedings of the 13th International Workshop on Distributed Algorithms (DISC), Bratislava, Slovakia (1999)
[10] Cheung, S. Y.; Ammar, M. H.; Ahamad, M., The grid protocol: A high performance scheme for maintaining replicated data, Proceedings of the 6th IEEE International Conference on Data Engineering (1990), p. 438-445
[11] Chvátal, V., The tail of the hypergeometric distribution, Discrete Math., 25, 285-287 (1979) · Zbl 0396.60016
[12] Cormen, T.; Leiserson, C.; Rivest, R., Introduction to Algorithms (1989), MIT Press: MIT Press Cambridge
[13] Demers, A.; Greene, D.; Hauser, C.; Irish, W.; Larson, J.; Shenker, S.; Sturgis, H.; Swine-hart, D.; Terry, D., Epidemic algorithms for replicated database maintenance, Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (1987), p. 1-12
[14] El Abbadi, A.; Toueg, S., Maintaining availability in partitioned replicated databases, ACM Trans. Database Systems, 14, 264-290 (1989)
[15] Feller, W., An Introduction to Probability Theory and Its Applications (1967), Wiley: Wiley New York · Zbl 0158.34902
[16] Garcia-Molina, H.; Barbara, D., How to assign votes in a distributed system, J. Assoc. Comput., 32, 841-860 (1985) · Zbl 0633.68109
[17] Gifford, D. K., Weighted voting for replicated data, Proceedings of the 7th Symposium on Operating Systems, Principles (1979), p. 150-162
[18] Haas, Z. J.; Liang, B., Ad hoc mobility management with uniform quorum systems, IEEE/ACM Trans. Networking, 7, 228-240 (1999)
[19] Hayden, M, and, Birman, K. P. 1995, Achieving Critical Reliability with Unreliable Components and Unreliable Glue, Cornell University Technical Report, TR95-1493, March.; Hayden, M, and, Birman, K. P. 1995, Achieving Critical Reliability with Unreliable Components and Unreliable Glue, Cornell University Technical Report, TR95-1493, March.
[20] Herlihy, M., A quorum-consensus replication method for abstract data types, ACM Trans. Comput. Systems, 4, 32-53 (1986)
[21] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602
[22] Israeli, A.; Shaham, A., Optimal multi-write multi-reader atomic register, Proceedings of the 11th ACM Symposium on Principles of Distributed Computing (1992), p. 71-82 · Zbl 1369.68053
[23] Krishnakumar, N.; Bernstein, A. J., Bounded ignorance: A technique for increasing concurrency in a replicated system, ACM Trans. Database Systems, 19, 586-625 (1994)
[24] Kedem, Z.; Palem, K.; Rabin, M.; Raghunathan, A., Efficient program transformations for resilient parallel computation via randomization, Proceedings of the 24th ACM Symposium on Theory of Computing (1992), p. 306-317
[25] Lamport, L., On interprocess communication (part II: algorithms), Distrib. Comput., 1, 86-101 (1986) · Zbl 0598.68023
[26] Maekawa, M., A □n algorithm for mutual exclusion in decentralized systems, ACM Trans. Comput. Systems, 3, 145-159 (1985)
[27] Malkhi, D.; Mansour, Y.; Reiter, M., On propagating updates in a Byzantine environment, Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems (1999), EPFL: EPFL Lausanne, p. 134-143
[28] Malkhi, D.; Merritt, M.; Rodeh, O., Secure multicast in a WAN, Distrib. Comput., 13, 19-28 (2000) · Zbl 1448.68146
[29] Malkhi, D.; Reiter, M., Byzantine quorum systems, Distrib. Comput., 11, 203-213 (1998) · Zbl 1448.68147
[30] Malkhi, D.; Reiter, M., Secure and scalable replication in Phalanx, Proceedings of the 17th IEEE Symposium on Reliable Distributed Systems (1998), p. 51-60
[31] Malkhi, D.; Reiter, M.; Wool, A., The load and availability of Byzantine quorum systems, SIAM J. Comput., 29, 1889-1906 (2000) · Zbl 1136.68334
[32] Malkhi, D.; Reiter, M.; Wright, R., Probabilistic quorum systems, Proceedings of the 16th ACM Symposium on Principles Distributed Computing (1997), p. 267-273 · Zbl 1373.68112
[33] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039
[34] Naor, M.; Wool, A., The load, capacity and availability of quorum systems, SIAM J. Comput., 27, 423-447 (1998) · Zbl 0911.60080
[35] Peleg, D.; Wool, A., The availability of quorum systems, Inform. and Comput., 123, 210-223 (1995) · Zbl 0839.68005
[36] Peleg, D., and Wool, A.1996, How to be an efficient snoop, or the probe complexity of quorum systems, inProceedings of the 15th ACM Symposium on Principles of Distributed Computing (PODC), pp. 290-299, Philadelphia.; Peleg, D., and Wool, A.1996, How to be an efficient snoop, or the probe complexity of quorum systems, inProceedings of the 15th ACM Symposium on Principles of Distributed Computing (PODC), pp. 290-299, Philadelphia. · Zbl 1321.68092
[37] Peleg, D.; Wool, A., Crumbling walls: A class of practical and efficient quorum systems, Distrib. Comput., 10, 87-98 (1997) · Zbl 1448.68350
[38] Pu, C., and Leff, A.1991, Replica control in distributed systems: An asynchronous approach, inProceedings of the 1991 ACM SIGMOD International Conference on Management of Data, pp. 377-386.; Pu, C., and Leff, A.1991, Replica control in distributed systems: An asynchronous approach, inProceedings of the 1991 ACM SIGMOD International Conference on Management of Data, pp. 377-386.
[39] Schmidt, J. P.; Siegel, A.; Srinivasan, A., Chernoff-Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math., 8, 223-250 (1995) · Zbl 0819.60032
[40] Thomas, R. H., A majority consensus approach to concurrency control for multiple copy databases, ACM Trans. Database Systems, 4, 180-209 (1979)
[41] Wong, M. H.; Agrawal, D., Tolerating bounded inconsistency for increasing concurrency in database systems, Proc. 11th ACM SIGACT-SIGMOD Symp. Princip. of Database Systems (PODS) (1992), p. 236-245
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.