Analysis of quorum-based protocols for distributed (k+1)-exclusion
Divyakant Agrawal, Ömer Eğeci̇oğlu, Amr El Abbadi · IEEE Transactions on Parallel and Distributed Systems · 1997
A generalization of the majority quorum for the solution of the distributed (k+1)-exclusion problem is proposed. This scheme produces a family of quorums of varying sizes and availabilities indexed by integral divisors r of k. The cases r=1 and r=k correspond to known majority based quorum generation algorithms MAJ and DIV, whereas intermediate values of r interpolate between these two extremes. A cost and availability analysis of the proposed methods is also presented. An interesting implication of this analysis is that in a reasonably reliable environment with a large number of sites, even protocols with low communication costs attain high availability.