The Load, Capacity, and Availability of Quorum Systems

A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information.Given a strategy to pick quorums, the load LS is the minimal access probability of the busiest element, minimizing over the strategies. The capacity \capS\ is the highest quorum accesses rate that cS can handle, so $\capS=1/\LS$.The availability of a quorum system cS is the probability that at least one quorum survives, assuming that each element fails independently with probability p. A tradeoff between LS and the availability of cS is shown.We present four novel constructions of quorum systems, all featuring optimal or near optimal load, and high availability. The best construction, based on paths in a grid, has a load of $O(1/\sqn)$, and a failure probability of $\exp(-\Omega(\sqn))$ when the elements fail with probability $p