(h, k)-arbiters for h-out-of-k mutual exclusion problem
h-Out-of-k mutual exclusion is a generalization of the I-mutual exclusion problem, where there are k units of shared resources and each process requests h (1 less than or equal to h less than or equal to k) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for I-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k + 1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k + 1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion. (C) 2003 Elsevier B.V. All rights reserved.
mutual exclusion quorum distributed algorithm arbiter