Analysis of Quorum-Based Protocols for Distributed (k+1)-Exclusion

A generalization of the majority quorum for the solution of the distributed(k+1)-exclusion problem is proposed. This scheme produces a family of quorumsof varying sizes and availabilities indexed by integral divisors r of k. Thecases r=1 and r=k correspond to known majority based quorum generationalgorithms MAJ and DIV, whereas intermediate values of r interpolate betweenthese two extremes. A cost and availability analysis of the proposed methodsis also presented. An interesting result of this analysis is that in areasonably reliable environment with a large number of sites, even protocolswith low communication costs attain high availability.