THE LOAD, CAPACITY, AND AVAILABILITY OF QUORUM SYSTEMS

A quorum system is a collection of sets (quorums) every two of which i ntersect. Quorum systems have been used for many applications in the a rea of distributed systems, including mutual exclusion, data replicati on, and dissemination of information. Given a strategy to pick quorums , the load L (S) is the minimal access probability of the busiest elem ent, minimizing over the strategies. The capacity S Cap(S) is the high est quorum accesses rate that can handle, so Cap(S) = 1/L(S). The S av ailability of a quorum S system L S S is the probability that at least one quorum survives, assuming that each element fails independently w ith probability p. A tradeoff between L () and the S availability of i s shown. We present S four novel constructions of quorum systems, all featuring optimal or near optimal load, and high availability. The bes t construction, based on paths in a grid, has a load of O(1/root n), a nd a failure probability of exp(-Omega(root n)) when the elements fail with probability p < 1/2. Moreover, even in the presence of faults, w ith exponentially high probability the load of this system is still O( 1/root n). The analysis of this scheme is based on percolation theory.