NONDOMINATED K-COTERIES FOR MULTIPLE MUTUAL EXCLUSION

被引:26
作者
NEILSEN, ML
MIZUNO, M
机构
[1] KANSAS STATE UNIV AGR & APPL SCI,DEPT COMP & INFORMAT SCI,MANHATTAN,KS 66506
[2] OKLAHOMA STATE UNIV,DEPT COMP SCI,STILLWATER,OK 74078
关键词
COTERIE; DISTRIBUTED COMPUTING; MUTUAL EXCLUSION; QUORUM; FAULT-TOLERANCE;
D O I
10.1016/0020-0190(94)00039-5
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Quorum-based mutual exclusion algorithms are resilient to node and communication line failures. In order to enter its critical section, a node must obtain permission from a quorum of nodes. A collection of quorums is called a coterie. The most resilient coteries are called nondominated coteries. Recently, k-coteries were proposed to be used in mutual exclusion algorithms that allow up to k entries to a critical section. In this paper, we introduce the notion of nondominated k-coteries. Then, we show that the most resilient k-coteries are nondominated. Finally, we present several simple methods to construct nondominated k-coteries. These methods include weighted voting and composition.
引用
收藏
页码:247 / 252
页数:6
相关论文
共 12 条
[1]   MUTUAL EXCLUSION IN PARTITIONED DISTRIBUTED SYSTEMS [J].
BARBARA, D ;
GARCIAMOLINA, H .
DISTRIBUTED COMPUTING, 1986, 1 (02) :119-132
[2]  
FUJITA S, 1991, LECT NOTES COMPUT SC, V557, P22
[3]   HOW TO ASSIGN VOTES IN A DISTRIBUTED SYSTEM [J].
GARCIAMOLINA, H ;
BARBARA, D .
JOURNAL OF THE ACM, 1985, 32 (04) :841-860
[4]  
GIFFORD DK, 1979, 7TH P S OP SYST PRIN, P150
[5]  
HUANG ST, 1993, 13TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS : PROCEEDINGS, P74, DOI 10.1109/ICDCS.1993.287721
[6]   AVAILABILITY OF KAPPA-COTERIE [J].
KAKUGAWA, H ;
FUJITA, S ;
YAMASHITA, M ;
AE, T .
IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (05) :553-558
[7]   A SQUARE-ROOT-N ALGORITHM FOR MUTUAL EXCLUSION IN DECENTRALIZED SYSTEMS [J].
MAEKAWA, M .
ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1985, 3 (02) :145-159
[8]  
NEILKSEN M, 1992, IEEE T PARALL DISTR, P582
[9]   A DISTRIBUTED ALGORITHM FOR MULTIPLE ENTRIES TO A CRITICAL SECTION [J].
RAYMOND, K .
INFORMATION PROCESSING LETTERS, 1989, 30 (04) :189-193
[10]  
RAYNAL M, 1991, P INT C COMPUTING IN