On Quorum Systems for Group Resources with Bounded Capacity


Authors


Abstract

We present a problem called (m,1,k)-resource allocation to model group mutual exclusion with bounded capacity. Specifically, the problem concerns the scheduling of a resource among m groups of processes. The resource can be used by at most k processes of the same group at a time, but no two processes of different groups can use the resource simultaneously. The problem reduces to group mutual exclusion when k is equal to the group size. We then generalize quorum systems for mutual exclusion to the problem. We show that the study of quorum systems for (m,1,k)-resource allocation is closely related to some classical problems in combinatorics and in finite projective geometries. By applying the results there, we are able to obtain some optimal/near-optimal quorum systems. We also exploit the properties of these systems pertaining to distributed computing.