Composite k-arbiters

The k-Arbiter is a useful concept to solve the distributed h-out-of-k mutua l exclusion problem. The distributed h-out-of-k mutual exclusion algorithms , based on the k-arbiter, have the benefits of high fault tolerance and low message cost. However, according to the definition of the k-arbiter, it is required to have a nonempty intersection among any (k + 1) quorums in a k- arbiter. Consequently, constructing k-arbiters is difficult. The coterie jo in operation proposed by Neilsen and Mizuno produces a new and larger coter ie by joining known coteries. In this paper, by extending the coterie join operation, we first propose a k-arbiter join operation to construct a new a nd larger k-arbiter from known k-arbiters for a large system. Then, we deri ve a necessary and sufficient condition for the k-arbiter join operation to construct a nondominated joined k-arbiter. Moreover, we discuss availabili ty properties of the joined k-arbiters. We observe that, by selecting prope r k-arbiters, the joined k-arbiter can provide a higher availability than t hat of the original input. Finally, we propose a k-arbiter compound operati on to construct k-arbiters by using coteries and/or k-coteries. By that way , the problem of constructing k-arbiters can be reduced to the problem of c onstructing coteries and/or k-coteries.