Distributed k-Mutual Exclusion Problem and k-Coteries
Distributed k-Mutual Exclusion Problem and k-Coteries
复制标题
分布式 k-互斥问题和 k-Coteries
DOI：
10.1007/3-540-54945-5_45
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
T. Ae
中科院分区：
文献类型：
--
作者：
S. Fujita;M. Yamashita;T. Ae
分布式k互斥问题是保证在一个临界区域内同时存在最多k个进程的问题。这个问题可以用k-coterie来解决：我们首先准备一个集合（k-coterie） C的集合（群体）Q的过程，使得C中群体的每个k集{Q1，⋯，Qk}包含一对Qi和Qj （i≠j）。希望进入临界区域的进程需要从C中quorum的每个成员那里获得许可，然后由于k-coterie的交叉特性，最多可以有k个进程进入临界区域，并且进入临界区域所需的（平均）消息数与C的（平均）quorum大小成比例。
The distributed k-mutual exclusion problem is the problem of guaranteeing that at most k processes are in a critical section simultaneously. This problem can be solved using the k-coterie: We first prepare a set (k-coterie) C of sets (quorums) Q of processes such that each k-set {Q1,⋯, Qk} of quorums in C contains a pair Qi and Qj (i≠j) intersecting each other. A process wishing to enter a critical section is required to collect a permission from each member of a quorum in C. Then at most k processes can be in a critical section because of the intersection property of k-coterie, and the (average) number of messages necessary for entering a critical section is in proportion to the (average) quorum size of C.