An Algorithm to construct nondominated k-coteries

Abstract

One of the solution in solving k mutual exclusion problem is the concept of k-coterie. A k-coterie under a set S is a set of subsets of S or quorums such that any k + 1 quorums, there are at least two quorums intersect each other. The k mutual exclusion problern is the problem of managing processes in such a way that at most k processes can enter their critical sections simultaneously. Nondominated k-coteries are more resilient to network and site failures than doninated k-coteries; that is the availability and reliability of a distributed system is better if nondominated k-coteries are used. Algorithms to construct k-coteries have been proposed, unfortunately they have some restrictions, especially in constructing nondominated k-coteries. The restrictions are due to the combination of N, the number of nodes in a distributed system, and k, the number of processes allowed to enter their critical sections simultaneously. To solve this problem, this paper proposes an algorithm to construct nondominated k-coteries for all combination of N and k.