The load, capacity and availability of quorum systems

A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. We investigate the load, capacity and availability of quorum systems. We present four novel constructions of quorum system, all featuring optimal or near optimal load, and high availability. These desirable properties of the constructions translate into improvements of any protocol using them: a low work load on the processors and a high resilience to processor failures. The best construction, based on paths in a grid, has a load of O(1/√n), and a failure probability of exp(-O(√n)) when the elements fail with probability p<½. Moreover, even in the presence of faults, with exponentially high probability the load of this system is still O(1/√n). The analysis of this scheme is based on Percolation Theory