Coterie Join Algorithm.
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 non empty 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.
Introduction
In computer systems, the problem of mutual exclusion is an important issue. In
a distributed environment, mutual exclusion protocols should gracefully tolerate
node and communication line failures. One such class of protocols may be constructed
based on coteries [6]. Given a set of nodes U in the system, a coterie
under U is a collection of subsets of U in which any two subsets have a nonempty
intersection. This property is called the intersection property. A subset of nodes
in a coterie is called a quorum [3, 7]. If a node acquires permission from all of the
nodes in any quorum, it may enter the critical section. Because of the intersection
property, at most one node may be in the critical section at any given time.
Garcia-Molina and Barbara classified coteries into two types: dominated and
nondominated [6]. Nondominated coteries are more resilient to network and site
failures than dominated coteries; that is, the availability and reliability of a distributed
system is better if nondominated coteries are used. They also defined a
function, called a coterie transformation, which may be used to derive new non-dominated
coteries from existing ones. Then, they presented a recursive algorithm
which uses the coterie transformation to partially enumerate nondominated coter-
ies for a given N , where j. The algorithm generates all of the nondominated
coteries which have corresponding vote assignments. However, the algorithm does
not enumerate all of the nondominated coteries for N ? 5. The purpose of the
algorithm is to partially enumerate nondominated coteries. Because of the large
number of nondominated coteries, the algorithm is not well suited for deriving
nondominated coteries for large N .
In this paper, we present an algorithm, called the join algorithm, which takes
nonempty coteries, as input, and returns a new, larger coterie. We show that
the algorithm produces a nondominated coterie if and only if the input coteries
are nondominated. Thus, dominated or nondominated coteries may be easily
constructed. The algorithm may be used to construct a coterie for large N .
In practice, it is not necessary to actually compute and store all of the quorums
in advance. Instead, we present an efficient method for determining whether a
given set of nodes contains a quorum, called the quorum containment test.
The method only uses the input coteries and information about how they are
joined.
Then, we show that the binary tree protocol, introduced by Agrawal and El
Abbadi [1] to derive coteries, is a special case of the join algorithm. Agrawal and
El Abbadi suggested that any k-ary tree may be used, instead of a binary tree.
We show that, in fact, the algorithm may be applied to any tree in which each
nonleaf node has at least two children. Furthermore, the resulting coteries are
nondominated.
The mutual exclusion problem can be generalized to the replica control prob-
lem. We show how the join algorithm may be applied to the replica control prob-
lem. In distributed systems, there are many occasions in which multiple replicas
are maintained. For instance, in a distributed database system, several copies of
each data item may be maintained at different sites to improve the reliability and
availability of the data. A replica control protocol is used to ensure that different
copies of an object appear to the user as a single nonreplicated object; that is,
objects are one-copy equivalent [5].
Agrawal and El Abbadi [2], and Herlihy [8] formalized the problem of replica
control in terms of read and write quorums. Barbara and Garcia-Molina formally
defined data structures, called quorum agreements, which may be used in quorum-based
replica control protocols [4]. A quorum agreement is a pair of sets (Q; Q
where Q and Q \Gamma1 are sets of subsets of U such that every subset in Q intersects
with every subset in Q \Gamma1 . We may consider Q to be a set of write quorums and
to be a set of read quorums. Equivalently, we may consider Q to be a set
of read quorums and Q \Gamma1 to be a set write quorums. We show that the join
algorithm may be applied to quorum agreements. The quorum containment test
may be used to determine if a given set of replicas contains a read or write quorum.
The organization of this paper is as follows: Section 2 reviews some important
definitions and properties about coteries presented by Garcia-Molina and Barbara.
The join algorithm and its properties are presented in Section 3. Applications
of the algorithm are also presented. In particular, the binary tree protocol is
generalized by using the join algorithm. Section 4 reviews quorum agreements
and shows that the join algorithm may be used to generate quorum agreements.
A Review of Coteries
denote the set of N nodes in the system. The term nodes
may refer to computers in a network or copies of a data object in a replicated
database. The following definitions, theorem, and examples are by Garcia-Molina
and Barbara [6]. A collection of sets C is a coterie under U iff
1.
2. (Intersection property): G; H 2 C
3. G;
The sets G 2 C are called quorums. Note that not all nodes must appear in a
coterie; that is, ffagg is a coterie under fa; b; cg. Let C and D be coteries under
U . Then, C dominates D iff
1. C 6= D.
2. For each H 2 D, there is a G 2 C such that G ' H.
A coterie D (under U) is dominated iff there is another coterie (under U) which
dominates D. If there is no such coterie, then D is nondominated. Note that
the empty coterie under U is nondominated iff ;. The following
theorem makes it easier to determine if a coterie is dominated.
Theorem 2.1: Let C be a coterie under a nonempty set U . Then, C is dominated
iff there exists a set H ' U such that:
1.
2. G 2 C
For example, let cgg. The set satisfies the properties
in Theorem 2.1. Hence, D is dominated by cgg. The coterie
C is nondominated. Note that coterie C is clearly better than D because all sets
of nodes which can operate under D, can also operate under C. Also, if only
nodes in fa; cg are available, a quorum can be formed in C, but not in D. Note
that D is also dominated by the coterie ffbgg.
3 Join Algorithm
The join algorithm provides a simple way of combining nonempty coteries to
construct new, larger coteries. In this section, the join algorithm and its properties
are introduced. Then, we present an efficient method for determining whether a
given set of nodes contains a quorum, without actually computing and storing all
of the quorums in advance. Finally, we apply the join algorithm to generate a
new class of coteries, called tree coteries. Tree coteries are a generalization of the
binary tree protocol introduced by Agrawal and El Abbadi [1].
3.1 The join algorithm
Let U 1 be a nonempty set of nodes and x 2 U 1 . Let U 2 be a nonempty set of
nodes such that U Given a coterie C 1 under
U 1 and a coterie C 2 under U 2 , a new coterie, C 3 under U 3 , may be constructed by
replacing each occurrence of x in quorums of C 1 by nodes in a quorum of C 2 . More
formally, let CU i
denote the set of all nonempty coteries under U i for
and define a function,
\Theta CU 2
, by
The function, T x , is called a coterie join function. A coterie constructed by using
a coterie join function is called a composite coterie; that is, C
is a composite coterie. All other nonempty coteries are called simple coteries.
For instance, simple coteries may be constructed by using weighted voting [7], the
grid protocol [2, 10], or some other method. The input coteries, C 1 and C 2 ,
may be either simple or composite. The join algorithm is to apply the coterie
join function, one or more times, to construct a composite coterie.
For example, let U 6g. Define the input
coteries,
is a coterie under U
constructed by replacing each occurrence of in quorums of C 1 by nodes in
quorums of C 2 .
Note that the above coteries, C are all nondominated. This is no
accident. In the following subsection, we will prove that combining two nonempty,
nondominated coteries results in a nondominated, composite coterie. We will also
prove some other properties that the join algorithm satisfies.
3.2 Properties of the algorithm
Let U 1 be a nonempty set of nodes and let x 2 U 1 . Let U 2 be a nonempty set of
nodes such that U be a nonempty
coterie under U i for 2. Let C
Theorem 3.1: C 3 is a coterie under U 3 .
Proof: First, we will show that G 3 6= ; and G 3 ' U 3 for any quorum G 3 2 C 3 .
Let G 3 2 C 3 . There are two cases to consider:
1. Suppose G
2. Suppose G
is a coterie, G 2 6= ;, and it follows that G 3 6= ;. Also,
since
Next, we will show that the intersection property is satisfied. Let G
We will show that G 3 " H 3 6= ;. There are four cases to consider:
1. Suppose G
2. Suppose G
;. Thus, there exists y
x
3. Suppose G
This case follows directly
from Case 2 (above).
4. Suppose G
quorum
Therefore, the intersection property holds.
Finally, we will show that minimality is satisfied. Let G 3 ; H 3 2 C 3 . We will show
that G 3 6ae H 3 . There are four cases to consider:
1. Suppose G
2. Suppose G
but x 62 G 1 . Thus, there exists y 2 G 1 such that y 62 H 1 , and y 6= x. Since
3. Suppose G
under
;. So, there exists y 2 G 2 such that y 62 H 3 . Since G 2 ' G 3 , y is
also in G 3 . Thus, G 3 6ae H 3 because y 2 G 3 , but y 62 H 3 .
4. Suppose G
and some quorum H
Since C 1 is a coterie, G 1 6ae H 1 . Thus, there exists y 2 G 1 such that y 62 H 1
or G
Since C 2 is a coterie, G 2 6ae H 2 . Thus, there exists z 2 G 2 such that z 62 H 2
or G
By comparing G 1 with H 1 and G 2 with H 2 , there are three cases to consider:
(a) Suppose G
(b) Suppose there exists y 2 G 1 such that y 62 H 1 and G
it follows that y 2 G 3 . Also, y
follows that y 62 H 3 . Thus, G 3 6ae H 3 .
(c) Suppose there exists z 2 G 2 such that z 62 H 2 . Then, z 2 G 3 and
z 62 H 3 . Thus, G 3 6ae H 3 .
Therefore, minimality holds and C 3 is a coterie under U 3 . 2
Theorem 3.2: If C 1 and C 2 are both nondominated, then C 3 is nondominated.
Proof: Assume that C 3 is dominated. By Theorem 2.1, there must exist a set
We will consider the relation between H 3 and the quorums in C 2 . There are two
cases to consider: either H 3 has at least one node in common with each quorum
in C 2 or there is a quorum G 2 in C 2 such that G
In each case, we will find a quorum G 02 C 3 such that G 0' H 3 to obtain a
contradiction.
1. Suppose G
So, there must exist a quorum G 0
would satisfy both properties in Theorem 2.1, and C 2 would be dominated.
We start by showing that G
quorums
then On the other hand, if x 62 G 1 , then
nondominated, there must exist a quorum G 0
Finally, by using quorum G 0
show that
there exists a quorum G 02 C 3 such that G 0' H 3 to obtain a contradiction.
There are only two possible cases to consider: either x 2 G 0
1 or x 62 G 0
1 .
This is a contradiction.
and This is a contradiction.
2. Suppose there exists G
We start by showing that G
Assume there is a quorum G There are two
cases to consider: either x 2 G 1 or x 62 G 1 . In each case, we will find a
quorum G 3 2 C 3 such that G 3 " H to obtain a contradiction.
because This is a contradiction.
This is
a contradiction.
Thus,
Since C 1 is nondominated, there exists a quorum G 0
would satisfy both properties in Theorem 2.1, and C 1
would be dominated. Since x 62 H 1 , it follows that x 62 G 0. Let G 0= G 0Then, G 02 C 3 . Since G 0' H 1 and H 1 ' H 3 , it follows that G 0' H 3 . This
is a contradiction.
Therefore, C 3 is nondominated. 2
Theorem 3.3: If C 1 is dominated, then C 3 is dominated.
Proof: To show that C 3 is dominated, we will construct a set H 3 satisfying the
properties in Theorem 2.1, that is G
dominated, by Theorem 2.1, there exists a set H 1 ' U 1 such that
There are only two possible
cases to consider: either x
1. Suppose x We
will show that G 3 " H 3
Let G 3 2 C 3 . There are two cases to consider:
First, we will show that G 3 "H 3 6= ;. By the definition of H 1 , G 1 "H 1 6=
;. Since x 62 G 1 , it follows that G 1 "(H
Next, we will show that G 3 6' H 3 . By the definition of H 1 , G 1 6' H 1 .
So, there exists y 2 G 1 such that y 62 H 1 , and y 6= x. Also, y
because y
because y 2 G 3 , but y 62 H 3 .
and some quorum G 2 2 C 2 .
First, we will show that G 3 "H 3 6= ;. Since C 2 is a coterie, G 2 "H 2 6= ;.
Thus,
Next, we will show that G 3 6' H 3 . Since G 1 6' H 1 , there exists y
such that y
2. Suppose x 62 H 1 . Let H We will show that G 3 "H 3
for all G 3 2 C 3 .
Let G 3 2 C 3 . There are two cases to consider:
By the definition of H 1 ,
and G 3 6' H 3 .
and some quorum G 2 2 C 2 .
First, we will show that G
it follows that
Next, we will show that G 3 6' H 3 . Since x
follows that
Thus,
Therefore, by Theorem 2.1, C 3 is dominated. 2
Theorem 3.4: If C 2 is dominated and x 2 G for some G 2 C 1 , then C 3 is
dominated.
Proof: Since C 2 is dominated, by Theorem 2.1, there exists a set H 2 ' U 2 such
that be a quorum in C 1 such
that x 2 H 1 and let H We will show that H 3 satisfies the
properties in Theorem 2.1, that is G
Let G 3 2 C 3 . There are two cases to consider:
1. Suppose G
First, we will show that G 3 " H 3 6= ;. Since H 1 2 C 1 and C 1 is a coterie,
Next, we will show that G 3 6' H 3 . Since x
Since C 1 is a coterie, G 1 6ae H 1 . Thus, G 1 6' H 1 . So, there exists a y 2 G 1
such that y 62
follows that G 3 6' H 3 because y 2 G 3 , but y 62 H 3 .
2. Suppose G
and some quorum G 2 2 C 2 .
First, we will show that G
Next, we will show that G 3 6' H 3 . From the definition of H 2 , we have G 2 6'
. So, there exists y 2 G 2 such that y 62 H 2 . Since G
and H
Thus,
Therefore, by Theorem 2.1, C 3 is dominated. 2
3.3 Example
Consider the following four nondominated coteries:
fc,ag g under
We may construct a new coterie by joining the above coteries as follows:
cg.
is a coterie under U cg.
f2,3,6,4g, f3,1,4,5g, f3,1,5,6g, f3,1,6,4g, f4,5,cg,
f5,6,cg, f6,4,cg, fc,1,2g, fc,2,3g, fc,3,1g g
C). Then, G is a coterie under 9g.
f2,3,6,4g, f3,1,4,5g, f3,1,5,6g, f3,1,6,4g, f4,5,7,8g,
f4,5,8,9g, f4,5,9,7g, f5,6,7,8g, f5,6,8,9g, f5,6,9,7g,
f6,4,7,8g, f6,4,8,9g, f6,4,9,7g, f7,8,1,2g, f8,9,1,2g,
f9,7,1,2g, f7,8,2,3g, f8,9,2,3g, f9,7,2,3g, f7,8,3,1g,
f8,9,3,1g, f9,7,3,1g g
By Theorem 3.2, the composite coterie G is nondominated.
3.4 Quorum containment test
As Garcia-Molina and Barbara have shown, the number of quorums may be exponential
in N [6]. In practice, to determine if a given set contains a quorum
of a composite coterie, it is not necessary to actually compute and store all of
the quorums of the composite coterie in advance. Instead, we only need to store
the input coteries used to construct the composite coterie and information about
how the composite coterie was constructed. This yields an efficient method for
determining if a given set of nodes, say S, contains a quorum G of the composite
coterie C. The following function, QC, called the quorum containment test,
returns true if there exists a quorum G 2 C such that G ' S, and false otherwise.
set of nodes, C
begin
then /* C is a composite coterie */
then return
else return
else /* C is a simple coterie */
if G ' S for some G 2 C
then return true
else return false
We assume that composite(C; x; C a function that returns true if
input parameter C is a composite coterie and false if C is a simple coterie. If C
is a composite coterie, as a side effect, the function also returns x; C
such that is a coterie under U 2 .
Consider the example, given in Section 3.3. Since B), the function
call returns true and also returns b; E; B, and UB
in Similarly, returns
false.
Since the construction of a composite coterie is determined statically, function
composite may be implemented by simple table indexing; therefore, it may be
performed in constant time. Let fC denote the set of simple input
coteries used to construct the composite coterie C, by applying the coterie join
function times. The time complexity of determining if a given set of
nodes, say S, contains a quorum, using the above function, is O(Mc) +O(Md),
where c is the maximum time required to determine if G ' S for any quorum
G in any simple input coterie, and d is the time required to compute the set
difference and union, possible implementation is to use bit
vectors to denote the sets and quorums. If the simple input coteries are coteries
under disjoint sets, it is not necessary to compute the set difference. Thus, the
time complexity becomes O(Mc).
Now, we present a simple example using the coteries given in Section 3.3.
Suppose we want to know if the set contains a quorum of G.
QC(S;G), where
(Note that QC(S;C) is true, because f9; 7g ' S.)
E)
(Note that QC(S 0 ; B) is false.)
(Note that QC(S 00 ; A) is true, because f3; 1g ' S 00 .)
true, because fa; ag 2 D.
Thus, S contains a quorum of G.
3.5 Tree coteries
The binary tree protocol was introduced by Agrawal and El Abbadi for use in
a distributed mutual exclusion algorithm [1]. The set of N nodes are logically
arranged in a complete binary tree. A path in the tree is a sequence of nodes
such that a i+1 is a child of a i . A quorum is constructed
by grouping all nodes on a path from the root node to a leaf node. If a node on
the path is not available, paths that start at both children and terminate at the
leaves may be used instead. They suggested that any k-ary tree, with k - 2, may
be used.
In fact, the algorithm may be applied to any tree in which each nonleaf node
has at least two children. The resulting coteries are called tree coteries. Note
that if a nonleaf node has only one child, then the resulting quorums do not satisfy
minimality.
'i'j
'i
'i'j
'i
'i
'i
6 'j
'i
'i'
ae
ae
ae
ae
Z
Z
Z
Z

Figure

1. Tree
Consider the tree shown in Figure 1. If all nodes are available, then any of
the following sets are quorums: f1,2,4g, f1,2,5g, f1,2,6g, f1,3,7g, and f1,3,8g. If
node 1 is unavailable, then paths from both children, nodes 2 and 3, may be used
instead. Thus, the sets f2,3,4,7g, f2,3,4,8g, f2,3,5,7g, f2,3,5,8g, f2,3,6,7g, and
f2,3,6,8g are quorums. If node 2 is unavailable, the set f1,4,5,6g is a quorum.
Likewise if node 3 is unavailable, the set f1,7,8g is a quorum. If both nodes 1
and 2 are unavailable, the sets f3,4,5,6,7g and f3,4,5,6,8g are quorums. Likewise,
if both nodes 1 and 3 are unavailable, the sets f2,4,7,8g, f2,5,7,8g, and f2,6,7,8g
are quorums. Finally, if nodes 1, 2, and 3 are unavailable, the set f4,5,6,7,8g is a
quorum. The set of all possible quorums is a tree coterie.
Tree coteries may be formally described within the framework of the join algo-
rithm. We start with a few definitions. Let be a set of n - 3
nodes. We define a tree coterie of depth two over U by
ng [
Node a 1 is viewed as the root node and the remaining nodes are viewed as leaf
nodes in the tree. Tree coteries are constructed by repeatedly joining tree coteries
of depth two together at one of the leaf nodes. Thus, any tree in which each
nonleaf node has at least two children may be constructed.
Theorem 3.5: Tree coteries of depth two, over a set of at least 3 nodes, are
nondominated coteries.
Proof: Let be a set of n - 3 nodes. Let
ng [
First, we will show that C is a coterie under U .
Clearly, if G 2 C, then G 6= ; and G ' U .
Next, we will show that the intersection property is satisfied. All quorums, except
for quorum g, include node a 1 . The quorum includes
all other nodes. Thus, the intersection property is satisfied.
Finally, we will show that minimality is satisfied. Clearly all quorums which
include node a 1 and one other node satisfy minimality. Also, any quorum which
includes node a 1 cannot be a subset of the quorum which does not include node
a 1 . So, the only possible violation of minimality that may occur is if the quorum
is a subset of a quorum which includes node a 1 . Since n - 3, the
quorum has at least two different elements, namely a 2 and a 3 , and
cannot be a subset of a quorum which includes node a 1 and only one other node.
Thus, minimality is satisfied.
Therefore, C is a coterie under U .
Next, we will show that C is nondominated. Assume that C is dominated. By
Theorem 2.1, there exists a set H ' U such that G " H 6= ; and G 6' H for all
quorums G 2 C.
There are two cases to consider: either a 1 2 H or a 1 62 H. In each case, we will
derive a contradiction.
1. Suppose a 1 2 H. Since there exists a k 2 U for
some k 6= 1 such that a k 2 H. Thus, This is a contradiction.
2. Suppose a 1 62 H. For
This is a contradiction.
Therefore, C is a nondominated coterie under U . 2
Theorem 3.6: Tree coteries are nondominated coteries.
Proof: By applying the join algorithm to tree coteries of depth two, it is easy to
see that any given tree coterie may be obtained. Therefore, by Theorems 3.1, 3.2,
and 3.5, tree coteries are nondominated coteries. 2
For example, consider the following tree coteries of depth two:
is a tree coterie under
This means that we simply append tree C 2 (shown in Figure 2b) to tree C 1 (shown
in Figure 2a) at node a, and append tree C 3 (shown in Figure 2b) to tree C 1 at
node b. This results in the tree shown in Figure 1.
'i'j
'i
a 'j
'i
ae
ae
ae
ae
Z
Z
Z
Z

Figure

2a. C 1
'i
'i'j
'i
'i
'i
6 'j
'i
'i'
Figure 2b. C 2 and C 3
4 Quorum Agreements
The mutual exclusion problem may be generalized to the replica control problem.
Agrawal and El Abaddi formalized the problem of replica control in terms of read
and write quorums [2]. Associated with each data object, (several) read and write
quorums are formed, each of which is a subset of all copies of the data object. A
read operation accesses all of the copies in a read quorum and the value of a copy
with the highest version number is returned. A write operation writes to all of
the copies in a write quorum and assigns each copy a version number that is one
more than the maximum number encountered in the write quorum. Let R and
W be sets of read and write quorums, respectively. In order to ensure one-copy
equivalence, the read and write quorums must satisfy two intersection properties:
G; H 2 W
2. Read-write
The write-write intersection property is necessary to ensure that each new version
number is larger than any previous version number.
The above protocol may be modified so that timestamps, generated by logical
clocks [9], are used instead of version numbers [8]. A read operation chooses the
copy with the largest timestamp, and a write operation assigns each copy a new
timestamp. In this protocol, only the read-write intersection property is required
to ensure one-copy equivalence. The write quorums do not have to intersect. If
different values of a data object are written to disjoint write quorums, future read
operations simply return the version with the largest timestamp.
Barbara and Garcia-Molina defined data structures, called quorum agree-
ments, which may be used in replica control protocols. The coterie join algorithm
may be used to generate quorum agreements.
4.1 A review of quorum agreements
First, we will briefly review quorum agreements. The definitions in this subsection
are by Barbara and Garcia-Molina [4].
A collection of sets, Q, is a quorum set under U iff
1. G 2 Q
2. (Minimality): G; H 2 Q
Let Q be a quorum set under U . Then, a complimentary quorum set, Q c , is
another quorum set under U such that G 2 Q and H 2 As
in previous literature, the sets G are informally called quorums, even
though they may not satisfy the definition given in Section 2.
There are many complimentary quorum sets corresponding to a given quorum
set. The antiquorum set of Q, denoted by Q \Gamma1 , is the complimentary quorum
set with the largest number of quorums of minimal size. Thus, we say that an
antiquorum set is maximal. That is, let
I
Qg.
The called a quorum agreement under U . There are
only three possible cases:
1. Q and Q are nondominated coteries, and
2. Q is a dominated coterie, and Q \Gamma1 is not a coterie (or equivalently, Q \Gamma1 is a
dominated coterie, and Q is not a coterie).
3. neither Q nor Q \Gamma1 is a coterie.
The first two types of quorum agreements may be used in replica control protocols
that use version numbers, and all three types may be used in replica control
protocols that use timestamps.
4.2 Application of the join algorithm
The join algorithm may be applied to generate quorum sets, complementary quorum
sets, and antiquorum sets.
Theorem 4.1: Let U 1 be a nonempty set of nodes and x 2 U 1 . Let U 2 be a
nonempty set of nodes such that U
be a quorum set under U 1 and Q c
1 be a complementary quorum set under U 1 . Let
be a quorum set under U 2 and Q cbe a complementary quorum set under U 2 .
Let
is a quorum set under U 3 ,
and Q cis a complementary quorum set under U 3 .
Proof: Note that the first property, G 3 2
follows directly from the proof given in Theorem 3.1.
Next, we will show that the intersection property is satisfied. Let G 3 2 Q 3 and
We will show that G 3 " H 3 6= ;. There are four cases to consider:
1. Suppose G
1 . Since
2. Suppose G
2 . There exists y
3. Suppose G
follows from Case 2 (above).
4. Suppose G
and H
Therefore, the intersection property holds.
Finally, minimality follows directly from the proof given in Theorem 3.1.
Therefore, Q 3 is a quorum set under U 3 , and Q cis a complementary quorum set
under U 3 . 2
Theorem 4.2: Let U 1 be a nonempty set of nodes and let x 2 U 1 . Let U 2 be a
nonempty set of nodes such that U
1 ) be a quorum agreement under U 1 and QA
a quorum agreement under U 2 . Let Q
3 ) is a quorum agreement under U 3 .
Proof: By Theorem 4.1, Q 3 is a quorum set under U 3 and Q \Gamma1is a complementary
quorum set under U 3 . We only need to show that Q
3 is maximal. Assume
that Q
3 is not maximal. Then, there is a set H 3 ' U 3 such that:
We will consider the relation between H 3 and quorums in Q 2 . There are two cases
to consider: either H 3 has at least one node in common with each quorum in Q 2
or there is a quorum G 2 in Q 2 such that G
In each case, we will find a quorum H 0
3 such that H 0
to obtain a
contradiction.
1. Suppose G
2 is an antiquorum set, there must exist a quorum H 0
2 such
that H 0' H 2 .
We start by showing that G
On the other hand, if x 62 G 1 , then G
for some G 3 2 Q 3 . Since G
Thus,
1 is an antiquorum set, there
exists H 0
1 such that H 0
Finally, by using H
2 , we will show that there exists
\Gamma1such that H 0' H 3 to obtain a contradiction. There are only two
possible cases to consider: either x
1 or x 62 H 0
1 .
3 , and
This
is a contradiction.
3 , and H 0' H 3 because
This is a contradiction.
2. Suppose that there exists G 2 2 Q 2 such that G 2 "H
We start by showing that G
Assume that there exists G There are two
cases to consider: either x 2 G 1 or x 62 G 1 . In each case, we will find
to obtain a contradiction.
because This is a contradiction.
This is
a contradiction.
Thus,
Since Q \Gamma1is an antiquorum set, there exists H 02 Q \Gamma1such that H 0' H 1 .
3 . Since
This is a contradiction.
Therefore,
3 is maximal, and QA 3 is a quorum agreement under U 3 . 2
Suppose that QA
3 ) is a quorum agreement constructed by using
the join algorithm to join quorum agreements QA
). The following conclusions may be made:
1. If both Q 1 and Q 2 are coteries, then Q 3 is a coterie.
2. If Q 1 and Q 2 are nondominated coteries, then Q 3 is a nondominated coterie.
Therefore, the join algorithm may be used to generate quorum agreements for both
types of replica control protocols: protocols based on timestamps and protocols
based on version numbers.
4.3 Example
In this subsection, we will give a simple example of how the join algorithm may
be used to generate a quorum agreement. Consider the two input quorum agree-
ments,
2gg.
If we use the join algorithm to construct a new quorum set, Q
then the corresponding antiquorum set is given by Q
1gg.
We obtain a new quorum agreement QA
3
The quorum containment test may be used for quorum sets, complementary
quorum sets, and antiquorum sets. Suppose we want to know if the set
contains a quorum of Q \Gamma1QC(S;Q \Gamma1
(Note that QC(S;Q \Gamma1
true, because f1; ag
1 .
Thus, S contains a quorum of Q \Gamma15 Conclusion
In this paper, we introduced the join algorithm which takes nonempty coteries,
as input, and returns a new, larger coterie. The algorithm produces a nondominated
coterie if and only if the input coteries are nondominated. The quorum
containment test provides an efficient method for determining if a given set of
nodes contains a quorum of a composite coterie. The test does not require that
the quorums of a composite coterie be computed in advance.
Within the framework of the join algorithm, we introduced tree coteries. Tree
coteries are a generalization of the binary tree protocol, introduced by Agrawal
and El Abbadi. We proved that tree coteries are nondominated.
The join algorithm may be used to generate quorum sets, complementary
quorum sets, and antiquorum sets. These structures may be used in a wide range
of distributed applications.



--R

An efficient solution to the distributed mutual exclusion problem.
Exploiting logical structures in replicated databases.
The vulnerability of vote assignments.
Mutual exclusion in partitioned distributed systems.
Concurrency Control and Recovery in Database Systems.
How to assign votes in a distributed system.
Weighted voting for replicated data.
A quorum consensus replication method for abstract data types.

A p N algorithm for mutual exclusion in decentralized systems.
--TR
How to assign votes in a distributed system
A quorum-consensus replication method for abstract data types
The vulnerability of vote assignments
Concurrency control and recovery in database systems
Efficient solution to the distributed mutual exclusion problem
Exploiting logical structures in replicated databases
A <inline-equation> <f> <rad><rcd>N</rcd></rad></f> </inline-equation> algorithm for mutual exclusion in decentralized systems
Time, clocks, and the ordering of events in a distributed system
Weighted voting for replicated data

--CTR
Her-Kun Chang , Shyan-Ming Yuan, Performance Characterization of the Tree Quorum Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.6 n.6, p.658-662, June 1995
Yiwei Chiao , Masaaki Mizuno , Mitchell L. Neilsen, A self-stabilizing quorum-based protocol for maxima computing, Distributed Computing, v.15 n.1, p.49-55, January 2002
P. C. Saxena , Sangita Gupta , Jagmohan Rai, A delay optimal coterie on the k-dimensional folded Petersen graph, Journal of Parallel and Distributed Computing, v.63 n.11, p.1026-1035, November
Yu-Chen Kuo, Composite k-Arbiters, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1134-1145, November 2001
Takashi Harada , Masafumi Yamashita, Improving the Availability of Mutual Exclusion Systems on Incomplete Networks, IEEE Transactions on Computers, v.48 n.7, p.744-747, July 1999
Yu-Chen Kuo , Shing-Tsaan Huang, Recognizing Nondominated Coteries and wr-Coteries by Availability, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.721-728, August 1998
Takashi Harada , Masafumi Yamashita, Transversal Merge Operation: A Nondominated Coterie Construction Method for Distributed Mutual Exclusion, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.183-192, February 2005
Takashi Harada , Masafumi Yamashita, Coterie Join Operation and Tree Structured k-Coteries, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.865-874, September 2001
Jan C. Bioch , Toshihide Ibaraki, Generating and Approximating Nondominated Coteries, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.905-914, September 1995
T. Ibaraki , T. Kameda, A Theory of Coteries: Mutual Exclusion in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.779-794, July 1993
Dahlia Malkhi , Michael Reiter , Avishai Wool, The load and availability of Byzantine quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.249-257, August 21-24, 1997, Santa Barbara, California, United States
P. C. Saxena , J. Rai, A survey of permission-based distributed mutual exclusion algorithms, Computer Standards & Interfaces, v.25 n.2, p.159-181, May
nonempty intersection;trees mathematics;index termsdistributed system;treecoteries;composite coterie;join algorithm;distributedalgorithms;read and write quorums;nonempty coteries;replica control protocol