K-ARBITER - A SAFE AND GENERAL SCHEME FOR H-OUT-OF-K MUTUAL EXCLUSION

Mutual exclusion is a well-known problem that arises when multiple pro cesses compete, in an uncoordinated way, for the acquisition of shared resources over a distributed system. In particular, k-mutual exclusio n allows at most k processes to get one unit of the same resource simu ltaneously. These paradigms do not cover all the cases in which resour ce accesses must be serialized over a distributed system. There exist cases (e.g. the bandwidth of communication lines) where the amount of shared resource might differ from request to request (for example, aud io and video communications). In this paper, we formalize this problem as the h-out of-k mutual exclusion problem, in which each request con cerns some number h (1 less than or equal to h less than or equal to k ) of units of shared resource and no unit is allocated to multiple pro cesses at the same time. Former simple and k-mutual algorithms cannot be used to solve this problem. We present a general scheme for a quoru m-based h-out of-k mutual exclusion algorithm that relies on a collect ion of quorums called k-arbiter. Several examples of k-arbiters are di scussed, two particular classes of k-arbiters are investigated and a m etric to evaluate the resiliency with respect to failures of k-arbiter s is also given.