Availability of k-Coterie
Availability of k-Coterie
复制标题
k-Coterie 的可用性
DOI：
10.1109/12.223674
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
T. Ae
中科院分区：
文献类型：
--
作者：
H. Kakugawa;S. Fujita;M. Yamashita;T. Ae
分布式k互斥问题（又称k互斥问题）是指在一个分布系统中，保证一次最多有k个进程能进入一个临界区域的问题。D. Barbara和H. Garcia-Molina（1987）提出的解决分布式互斥问题（即1-互斥问题）的方法是对多数共识的扩展，并使用了群体。基于小窝的1互斥锁算法的优劣很大程度上取决于小窝的可用性，并且已经证明在这种意义上大多数小窝是最优的，前提是：网络拓扑是完全图，链路永远不会失败，并且过程的可靠性p至少为1/2。为了解决k-互斥问题，引入了k-群的扩展——k-群的概念，并导出了k-多数群的自然扩展——k-多数群在条件(1)-(3)下的最优可靠性p的下界和上界。例如，当k=3时，p必须大于0.994才能使k多数群体达到最优。>
The distributed k-mutual-exclusion problem (k-mutex problem) is the problem of guaranteeing that at most k processes at a time can enter a critical section at a time in a distribution system. A method proposed for the solution of the distributed mutual exclusion problem (i.e., 1-mutex problem) by D. Barbara and H. Garcia-Molina (1987) is an extension of majority consensus and uses coteries. The goodness of coterie-based 1-mutex algorithm strongly depends on the availability of coterie, and it has been shown that majority coterie is optimal in this sense, provided that: the network topology is a complete graph, the links never fail, and p, the reliability of the process, is at least 1/2. The concept of a k-coterie, an extension of a coterie, is introduced for solving the k-mutex problem, and lower and upper bounds are derived on the reliability p for k-majority coterie, a natural extension of majority coterie, to be optimal, under conditions (1)-(3). For example, when k=3, p must be greater than 0.994 for k-majority coterie to be optimal. >