An Algorithm to construct nondominated k-coteries

Rikip Ginanjar, Nur Hadisukmana


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.


Coterie; Mutual Exclusion; Nondominated; Quorum


H. Garcia-Monila and D. Barbara. How to assign votes in a distributed system. Journal of A CM, 32(4):841-860, 1985

S.T. Huang, .J.R. Jiang, and Y.C. Kuo. k-coteries for fault k entries to a critical section. IEEE 13th International Conference on Disiributed Computing Systems, pages 74-81, 1993.

H. Kokugawa, S. Fujita, M. Yamashita, and T. Ae. A distributed k-mutual exclusion algorithm using k-coterie. 2nd International Symposium on Algorithms (LNCS 557), pages 22-:31, 1991.

H. Kokugawa, S. Fujita, M. Yamasluta, and T. Ac. Availability of kcoterie. IEEE Transactions on Computers, 42(5):553-55S, 1993.

S. Fujita and M. Yamashita. Constructing asymptotically optimal k-coterie. In The Proceeding of Th 2nd International Syniposium on Algorithms, 1991.

M.L. Neilsen and M. Mizuno. Coterie join algorithm. IEEE Trans actions on Parallel and Distributed Systems, 3(5):582-590, 1992.

M.L. Neilsen and M. Mizuno. Nondominated k-coterie for multiple exclusion. Information Processing Lctters, 50(5):247-252, 1994

D. Barbara and FT. Garcia-Molina. The reliability of votiug mechanisms. IEEE Trans actions on Computers, C-36(1O):1 197-1208, 1987.

T. Ibaraki and T. Kaineda. A theory of coteries: Mutual exclusion in distributed systems. IEEE Transactions on Parallel and Distributed Systems. 4(7):779-793, 1993.

Yu-Chen Kuo and Po-Yao Wu. The Availability of Complemental k-Coteries. The Computer Journal, Vol. 51 No. 6, 2008.

La Ode Muhlis, Armin Lawi, Amir Kamal Amir. Operasi Join Koteri-k Diperluas. Jurnal Matematik. Statistik dan Komputasi. Vol 14 No.2, pages 106-113. 2018

Total views : 39 times


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

shopify stats IJEECS visitor statistics