Coterie Join Algorithm
Coterie Join Algorithm
复制标题
小圈子加入算法
DOI：
10.1109/71.159041
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
M. Mizuno
中科院分区：
文献类型：
--
作者：
M. Neilsen;M. Mizuno
给定分布式系统中的一组节点，小圈子是该节点集的子集的集合，使得任何两个子集都有非空交集并且彼此不正确包含。一个小圈子中的节点子集称为一个仲裁。一个算法，称为连接算法，它采取非空的小圈子作为输入，并返回一个新的，更大的小圈子称为复合小圈子介绍。证明了一个复合小圈子是非支配的当且仅当输入小圈子是非支配的。使用该算法，可以很容易地为大量的节点构造支配或非支配圈。提出了一种确定给定节点集是否包含复合小圈子的有效方法。作为一个例子，利用连接算法推广了树的圈，并证明了树的圈是非支配的。它示出的加入算法可以被用来生成读和写法定人数，可以使用的副本控制协议。>
Given a set of nodes in a distributed system, a coterie is a collection of subsets of the set of nodes such that any two subsets have a nonempty intersection and are not properly contained in one another. A subset of nodes in a coterie is called a quorum. An algorithm, called the join algorithm, which takes nonempty coteries as input, and returns a new, larger coterie called a composite coterie is introduced. It is proved that a composite coterie is nondominated if and only if the input coteries are nondominated. Using the algorithm, dominated or nondominated coteries may be easily constructed for a large number of nodes. An efficient method for determining whether a given set of nodes contains a quorum of a composite coterie is presented. As an example, tree coteries are generalized using the join algorithm, and it is proved that tree coteries are nondominated. It is shown that the join algorithm may be used to generate read and write quorums which may be used by a replica control protocol. >