DocumentCode :
824248
Title :
Coterie join algorithm
Author :
Neilsen, Mitchell L. ; Mizuno, Masaaki
Author_Institution :
Dept. of Comput. & Inf. Sci., Kansas State Univ., Manhattan, KS, USA
Volume :
3
Issue :
5
fYear :
1992
fDate :
9/1/1992 12:00:00 AM
Firstpage :
582
Lastpage :
590
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;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.159041
Filename :
159041
Link To Document :
بازگشت