A quorum system is a collection S of sets (quorums), every two of which intersect. Quorum systems have been used for many applications in distributed systems including mutual exclusion, data replication and dissemination of information.
Given a strategy to pick quorums, the load L(S) is the minimal access probability of the busiest element, minimizing over the strategies. The capacity cap(S) is the highest quorum accesses rate that S can handle. We show that for any quorum system, cap(S)=1/L(S).
The availability of a quorum system S is the probability that at least one quorum survives, assuming the elements fail independently with probability p. A tradeoff between L(S) and the availability of S is shown.
We present four novel constructions of quorum systems, all featuring optimal or near optimal load, and high availability. The best construction, partly inspired in by the game of hex, is based on paths in a grid. Is load is O(1/sqrt(n)) (the best possible), and the failure probability is exponentially small with sqrt(n), assuming the elements fail with probability p<1/2. With exponentially high probability, the load of this system is still O(1/sqrt(n)) even in the presence of faults. The analysis of this scheme is based on Percolation Theory.
Postscript, gzipped Postscript.
Related On-Line Papers: