On quorum systems for group resources allocation

摘要

We present a problem, called (n,m,k,d)-resource allocation, to model allocation of group resources with bounded capacity. Specifically, the problem concerns the scheduling of k identical resources among n processes which belong to m groups. Each resource can be used by at most d processes of the same group at a time, but no two processes of different groups can use a resource simultaneously. The problem captures two fundamental types of conflicts in mutual exclusion: k-exclusion's amount constraint on the number of processes that can share a resource, and group mutual exclusion's type constraint on the class of processes that can share a resource. We then study the problem in the message passing paradigm, and investigate quorum systems for the problem. We begin by establishing some basic and general results for quorum systems for the case of k = 1, based on which quorum systems for the general case can be understood and constructed. We found that the study of quorum systems for (n, m, 1, d) -resource allocation is related to some classical problems in combinatorics and in finite pro-jective geometries. By applying the results there, we are able to obtain some optimalear-optimal quorum systems.