(h; k)-arbiters for h-out of-k Mutual Exclusion Problem
Yoshifumi Manabe, Naka Tajima · 2016
h-out of-k mutual exclusion is a generalization of 1-mutual exclusion problem, where there are k units of shared resources and each process requests h(1 h 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 these in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. 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 corre-sponding k-arbiter; consequently using the (h; k)-arbiters is more efficient than using the k-arbiters. Uniform (h; k)-arbiter is an optimal generalization of the majority coterie for 1-mutual exclusion. (k + 1)-cube (h; k)-arbiter is a quasi-optimal generalization of square grid coterie for 1-mutual exclusion. 1.