Title :
Coterie join algorithm
Author :
Neilsen, Mitchell L. ; Mizuno, Masaaki
Author_Institution :
Dept. of Comput. & Inf. Sci., Kansas State Univ., Manhattan, KS, USA
fDate :
9/1/1992 12:00:00 AM
Abstract :
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
Keywords :
distributed algorithms; trees (mathematics); composite coterie; distributed system; join algorithm; nonempty coteries; nonempty intersection; read and write quorums; replica control protocol; tree coteries; Availability; Binary trees; Concurrent computing; Distributed computing; Fault tolerance; Permission; Protocols; Testing; Voting;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on