Byzantine quorum systems.
Quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure of data repositories. In this paper we consider the arbitrary (Byzantine) failure of data repositories and present the first study of quorum system requirements and constructions that ensure data availability and consistency despite these failures. We also consider the load associated with our quorum systems, i.e., the minimal access probability of the busiest server. For services subject to arbitrary failures, we demonstrate quorum systems over <i>n</i> servers with a load of <i>O</i>(1/<i>n</i>), thus meeting the lower bound on load for benignly fault-tolerant quorum systems. We explore several variations of our quorum systems and extend our constructions to cope with arbitrary client failures.
Introduction
A well known way to enhance the availability and performance of a replicated service is by using
quorums . A quorum system for a universe of servers is a collection of subsets of servers, each pair
of which intersect. Intuitively, each quorum can operate on behalf of the system, thus increasing
its availability and performance, while the intersection property guarantees that operations done
on distinct quorums preserve consistency.
In this paper we consider the arbitrary (Byzantine) failure of clients and servers, and initiate the
study of quorum systems in this model. Intuitively, a quorum system tolerant of Byzantine failures
is a collection of subsets of servers, each pair of which intersect in a set containing sufficiently many
correct servers to guarantee consistency of the replicated data as seen by clients. We provide the
following contributions.
1. We define the class of masking quorum systems, with which data can be consistently replicated
in a way that is resilient to the arbitrary failure of data repositories. We present several
example constructions of such systems and show necessary and sufficient conditions for the
existence of masking quorum systems under different failure assumptions.
2. We explore two variations of masking quorum systems. The first, called dissemination quorum
systems, is suited for services that receive and distribute self-verifying information from correct
clients (e.g., digitally signed values) that faulty servers can fail to redistribute but cannot
undetectably alter. The second variation, called opaque masking quorum systems, is similar
to regular masking quorums in that it makes no assumption of self-verifying data, but it
differs in that clients do not need to know the failure scenarios for which the service was
designed. This somewhat simplifies the client protocol and, in the case that the failures
are maliciously induced, reveals less information to clients that could guide an adversary
attempting to compromise the system.
3. We explore the load of each type of quorum system, where the load of a quorum system is
the minimal access probability of the busiest server, minimizing over all strategies for picking
quorums. We present a masking quorum system with the property that its load over a total
of n servers is O( 1
thereby meeting the lower bound for the load of benignly-fault-tolerant
quorum systems. As an added contribution, we also provide a proof of this lower bound for
benignly-fault-tolerant quorum systems-and, a fortiori, Byzantine quorum systems-that is
much simpler than previous proofs. For opaque masking quorum systems, we prove a lower
bound of 1
2 on the load, and present a construction that meets this lower bound and proves
it tight.
4. For services that use masking quorums (opaque or not), we show how to deal with faulty
clients in addition to faulty servers. The primary challenge raised by client failures is that
there is no guarantee that clients will update quorums according to any specified protocol.
Thus, a faulty client could leave the service in an inconsistent and irrecoverable state. We
develop two update protocols, by which clients access the replicated service, that prevent
clients from leaving the service in an inconsistent state. Both protocols have the desirable
property that they involve only the quorum at which an access is attempted, while providing
system-wide consistency properties.
In our treatment, we express assumptions about possible failures in the system in the form of
a fail-prone system of servers, such that some B i contains all the faulty servers.
This formulation includes typical failure assumptions that at most a threshold f of servers fail
(e.g., the sets could be all sets of f servers), but it also generalizes to allow less uniform
failure scenarios. Our motivation for exploring this generalization stems from our experience in
constructing secure distributed services [Rei96, MR96], i.e., distributed services that can tolerate
the malicious corruption of some (typically, up to a threshold number of) component servers by an
attacker. A criticism to assuming a simple threshold of corrupted servers is that server penetrations
may not be independent. For example, servers in physical proximity to each other or in the
same administrative domain may exhibit correlated probabilities of being captured, or servers
with identical hardware and software platforms may have correlated probabilities of electronic
penetration. By exploiting such correlations (i.e., knowledge of the collection B), we can design
quorum systems that more effectively mask faulty servers.
Our quorum systems, if used in conjunction with appropriate protocols and synchronization
mechanisms, can be used to implement a wide range of data semantics. In this paper, however,
we choose to demonstrate a variable supporting read and write operations with relatively weak
semantics, in order to maintain focus on our quorum constructions. These semantics imply a safe
variable [Lam86] in the case of a single reader and single writer, which a set of correct clients can use
to build other abstractions, e.g., atomic, multi-writer multi-reader registers [Lam86, IS92, LTV96],
concurrent timestamp systems [DS89, IL93], l-exclusion [DGS88, ADGM90], and atomic snapshot
scan [ADGM93, And93]. Our quorum constructions can also be directly exploited in algorithms that
employ "uniform" quorums for fault tolerance either explicitly or implicitly (by involving a threshold
of processes), in order to tolerate non-uniform failure scenarios. Examples include algorithms for
shared memory emulation [ABD95], randomized Byzantine agreement [Tou84], reliable Byzantine
multicast [BT85, Rei94, MR96], and secure replicated data [HT88].
The rest of this paper is structured as follows. We begin in Section 2 with a description of related
work. In Section 3 we present our system model and definitions. We present quorum systems for
the replication of arbitrary data subject to arbitrary server failures in Section 4, and in Section 5
we present two variations of these systems. We then detail access protocols for replicated services
that tolerate faulty clients in addition to faulty servers in Section 6. We conclude in Section 7.
Related work
Our work was influenced by the substantial body of literature on quorum systems for benign failures
and applications that make use of them, e.g., [Gif79, Tho79, Mae85, GB85, Her86, ET89, CAA90,
AE91, NW94, PW95]. In particular, our grid construction of Section 5.1 was influenced by grid-like
constructions for benign failures (e.g., [CAA90]), and we borrow our definitions of domination and
load from [GB85] and [NW94], respectively.
Quorum systems have been previously employed in the implementation of security mechanisms.
Naor and Wool [NW96] described methods to construct an access-control service using quorums.
Their constructions use cryptographic techniques to ensure that out-of-date (but correct) servers
cannot grant access to unauthorized users. Agrawal and El Abbadi [AE90] and Mukkamala [Muk94]
considered the confidentiality of replicated data despite the disclosure of the contents of a threshold
of the (otherwise correct) repositories. Their constructions used quorums with increased intersec-
tion, combined with Rabin's dispersal scheme [Rab89], to enhance the confidentiality and availability
of the data despite some servers crashing or their contents being observed. Our work differs
from all of the above by considering arbitrarily faulty servers, and accommodating failure scenarios
beyond a simple threshold of servers.
Herlihy and Tygar [HT88] applied quorums with increased intersection to the problem of protecting
the confidentiality and integrity of replicated data against a threshold of arbitrarily faulty
servers. In their constructions, replicated data is stored encrypted under a key that is shared among
the servers using a threshold secret-sharing scheme [Sha79], and each client accesses a threshold
number of servers to reconstruct the key prior to performing (encrypted) reads and writes. This
construction exhibits one approach to make replicated data self-verifying via encryption, and consequently
the quorum system they develop is a special case of our dissemination quorum systems,
i.e., for a threshold of faulty servers.
Other techniques have been proposed for constructing distributed services that tolerate the
arbitrary failure of some component servers, e.g., see [Sch90, Mar90, RB94]. Such techniques of
which we are aware typically require that all servers receive and process all client accesses, and
thus they exhibit high load. In many cases, our techniques could be used to more efficiently mask
arbitrary failures.
3 Preliminaries
3.1 System model
We assume a universe U of servers, jU an arbitrary number of clients that are distinct
from the servers. A quorum system Q ' 2 U is a set of subsets of U , any pair of which intersect.
Each called a quorum.
Servers (and clients) that obey their specifications are correct. A faulty server, however, may
deviate from its specification arbitrarily. A fail-prone system B ' 2 U is a set of subsets of U ,
none of which is contained in another, such that some contains all the faulty servers. The
fail-prone system represents an assumption characterizing the failure scenarios that can occur, and
could express typical assumptions that up to a threshold of servers fail, as well as less uniform
assumptions.
In the remainder of this section, and throughout Sections 4 and 5, we assume that clients behave
correctly. In Section 6 we will relax this assumption (and will be explicit when we do so).
We assume that any two correct processes (clients or servers) can communicate over an au-
thenticated, reliable channel. That is, a correct process receives a message from another correct
process if and only if the other correct process sent it. However, we do not assume known bounds
on message transmission times; i.e., communication is asynchronous.
3.2 Access protocol
We consider a problem in which the clients perform read and write operations on a variable x that
is replicated at each server in the universe U . For the purposes of this paper, we define correctness
of this variable as follows; a more formal treatment of these concepts can be found in [Lam86]. We
say that a read or write operation op 1 precedes an operation op 2 if op 1 terminates (in real time, at
the client that initiated it) before op 2 starts (in real time, at the client initiating it). If op 1 does not
precede op 2 and op 2 does not precede op 1 , then they are called concurrent. Given a set of operations,
a serialization of those operations is a total ordering on them that extends the precedence ordering
among them. Then, our correctness condition requires that any read that is concurrent with no
writes returns the last value written in some serialization of the preceding writes. In the case of a
single-reader, single-writer variable, this will immediately imply safe semantics [Lam86].
Copies of the variable x are stored at each server, along with a timestamp value t. Timestamps
are assigned by a client to each replica of the variable when the client writes the replica. Our
protocols require that different clients choose different timestamps, and thus each client c chooses
its timestamps from some set T c that does not intersect T c 0 for any other client c 0 . The timestamps
in T c can be formed, e.g., as integers appended with the name of c in the low-order bits. The read
and write operations are implemented as follows.
Write: For a client c to write the value v, it queries each server in some quorum Q to obtain a
set of value/timestamp pairs chooses a timestamp t 2 T c greater than the
highest timestamp value in A and greater than any timestamp it has chosen in the past; and
updates x and the associated timestamp at each server in Q to v and t, respectively.
Read: For a client to read x, it queries each server in some quorum Q to obtain a set of
. The client then applies a deterministic function
Result() to A to obtain the result Result(A) of the read operation.
In the case of a write operation, each server updates its local variable and timestamp to the received
values !v; t? only if t is greater than the timestamp currently associated with the variable.
Two points about this description deserve further discussion. First, the nature of the quorum
sets Q and the function Result() are intentionally left unspecified; further clarification of these
are the point of this paper. Second, this description is intended to require a client to obtain
a set A containing value/timestamp pairs from every server in some quorum Q. That is, if a
client is unable to gather a complete set A for a quorum, e.g., because some server in the quorum
appears unresponsive, the client must try to perform the operation with a different quorum. This
requirement stems from our lack of synchrony assumptions on the network: in general, the only
way that a client can know that it has accessed every correct server in a quorum is to (apparently
successfully) access every server in the quorum. Our framework guarantees the availability of a
quorum at any moment, and thus by attempting the operation at multiple quorums, a client can
eventually make progress. In some cases, the client can achieve progress by incrementally accessing
servers until it obtains responses from a quorum of them.
3.3 Load
A measure of the inherent performance of a quorum system is its load. Naor and Wool [NW94]
define the load of a quorum system as the probability of accessing the busiest server in the best
case. More precisely, given a quorum system Q, an access strategy w is a probability distribution
on the elements of Q; i.e.,
1. w(Q) is the probability that quorum Q will be chosen
when the service is accessed. Load is then defined as follows:
Definition 3.1 Let a strategy w be given for a quorum system over a universe
U . For an element u 2 U , the load induced by w on u is l w
The load induced
by a strategy w on a quorum system Q is
The system load on a quorum system Q is
where the minimum is taken over all strategies. 2
We reiterate that the load is a best case definition. The load of the quorum system will be
achieved only if an optimal access strategy is used, and only in the case that no failures occur. A
strength of this definition is that load is a property of a quorum system, and not of the protocol
using it.
A comparison of the definition of load to other seemingly plausible definitions is given in [NW94].
They also explore a related notion, the capacity of a quorum system, which is the rate at which
the system handles quorum accesses. They further prove that capacity is the inverse of load.
3.4 Size and Domination
Another natural measure of the performance of a quorum system is the size of its quorums. Intu-
itively, the size of a quorum represents the cost incurred by a client when accessing it. Thus, in
general, smaller quorums are more desirable.
Of special interest are quorum systems that cannot be reduced in size (i.e., that no quorum in
the system can be reduced in size). Such quorum systems are called non-dominated. More precisely,
let a coterie be a quorum system Q with the property that if Q
that Q; Q 0 are two coteries, Q , such that for every Q there exists a Q 2 Q such that
dominated if there exists a coterie Q that dominates it, and
is non-dominated if no such coterie exists. In this paper we consider only coteries, although some
of our constructions will be dominated.
Masking quorum systems
In this section we introduce masking quorum systems, which can be used to mask the arbitrarily
faulty behavior of data repositories. To motivate our definition, suppose that the replicated variable
x is written with quorum Q 1 , and that subsequently x is read using quorum Q 2 . If B is the set of
arbitrarily faulty servers, then (Q 1 "Q 2 )nB is the set of correct servers that possess the latest value
for x. In order for the client to obtain this value, the client must be able to locate a value/timestamp
pair returned by a set of servers that could not all be faulty. In addition, for availability we require
that there be no set of faulty servers that can disable all quorums.
Definition 4.1 A quorum system Q is a masking quorum system for a fail-prone system B if the
following properties are satisfied.
;It is not difficult to verify that a masking quorum system enables a client to obtain the correct
answer from the service. The write operation is implemented as described in Section 3, and the
read operation becomes:
Read: For a client to read a variable x, it queries each server in some quorum Q to obtain a set
of value/timestamp pairs . The client computes the set
The client then chooses the pair !v; t? in A 0 with the highest timestamp, and chooses v as
the result of the read operation; if A 0 is empty, the client returns ? (a null value).
Lemma 4.1 A read operation that is concurrent with no write operations returns the value written
by the last preceding write operation in some serialization of all preceding write operations.
Proof. Let W denote the set of write operations preceding the read. The read operation will
return the value written in the write operation in W with the highest timestamp, since, by the
construction of masking quorum systems, this value/timestamp pair will appear in A 0 and will have
the highest timestamp in A 0 (any pair with a higher timestamp will be returned only by servers in
B). So, it suffices to argue that there is a serialization of the writes in W in which this
operation appears last, or in other words, that this write operation precedes no other write
operation in W . This is immediate, however, as if it did precede another write operation in W ,
that write operation would have a higher timestamp. 2
The above lemma implies that the protocol above implements a single-writer single-reader safe
variable [Lam86]. From these, multi-writer multi-reader atomic variables can be built using well-known
constructions [Lam86, IS92, LTV96].
A necessary and sufficient condition for the existence of a masking quorum system (and a
construction for one, if it exists) for any given fail-prone system B is given in the following theorem:
Theorem 4.1 Let B be a fail-prone system for a universe U . Then there exists a masking quorum
system for B iff Bg is a masking quorum system for B.
Proof. Obviously, if Q is a masking quorum system for B, then one exists. To show the converse,
assume that Q is not a masking quorum. Since M2 holds in Q by construction, there exist
B, such that . By
the construction of Q, we know that any masking quorum system for B
must contain quorums Q 0
. However, for any such Q 0
, it is the case that
. Also, since Q 0
2 , we have
violating M1. Therefore, there does not exist a masking quorum
system for B under the assumption that Q is not a masking quorum system for B. 2
Corollary 4.1 Let B be a fail-prone system for a universe U . Then there exists a masking quorum
system for B iff for all In particular, suppose that
fg. Then, there exists a masking quorum system for B iff n ? 4f .
Proof. By Theorem 4.1, there is a masking quorum for B iff Bg is a masking
quorum for B. By construction, Q is a masking quorum iff M1 holds for Q, i.e., iff for all
proved in [NW94] for benign-failure quorum systems, and holds for
masking quorums as well (as a result of M1). Let c(Q) denote the size of the smallest quorum of
Q.
Theorem 4.2 If Q is a quorum system over a universe of n elements, then L(Q) - maxf 1
c(Q)
g.
The proof of this theorem in [NW94] employs rather complex methods. Here we present a simpler
proof of their theorem.
Proof. Let w be any strategy for the quorum system Q, and fix
Summing the loads induced by w on all the elements of Q 1 we obtain:
l w
Therefore, there exists some element in Q 1 that suffers a load of at least 1
c(Q)
Similarly, summing the total load induced by w on all of the elements of the universe, we get:
u2U
l w
u2U
(Here, the inequality results from the minimality of c(Q).) Therefore, there exists some element in
U that suffers a load of at least c(Q)
Since any masking quorum system is a quorum system, we have, a fortiori:
Corollary 4.2 If Q is a masking quorum system over a universe of n elements, then L(Q) -
c(Q)
n g and thus L(Q) - 1
n .
Below we give several examples of masking quorum systems and describe their properties. When
we refer to a system as non-dominated, we mean within the class of masking quorum systems for
the given fail-prone system B.
Example 4.1 (Threshold) Suppose that Note that this
corresponds to the usual threshold assumption that up to f servers may fail. Then, the quorum
system is a masking quorum system for B. M1 is satisfied because
any Q intersect in at least 2f +1 elements. M2 holds because d n+2f+1e - This
system is non-dominated, and a strategy that assigns equal probability to each quorum induces a
load of 1
2 e on the system. By Corollary 4.2, this load is in fact the load of the system. 2
The following example is interesting since its load decreases as a function of n, and since it
demonstrates a method for ensuring system-wide consistency in the face of Byzantine failures while
requiring the involvement of fewer than a majority of the correct servers.
Example 4.2 (Grid quorums) Suppose that the universe of servers is of size
integer k and that
n. Arrange the universe into a
n \Theta
grid, as shown in Figure 1. Denote the rows and columns of the grid by R i and C i , respectively,
n. Then, the quorum system
i2I
is a masking quorum system for B. M1 holds since every pair of quorums intersect in at least 2f +1
elements (the column of one quorum intersects the 2f rows of the other), and M2 holds since
for any choice of f faulty elements in the grid, 2f full rows and a column remain available.
A strategy that assigns equal probability to each quorum induces a load of (2f+2)
n , and
again by Corollary 4.2, this is the load of the system. 2
Note that by choosing in the example above, the resulting construction
has a load of O( 1
which asymptotically meets the bounds given in Corollary 4.2.
The grid construction above is dominated: e.g., all of the column elements above the top row in
each quorum can be removed (and the quorum system remains dominated). The grid construction
would work for some non-square grids as well, e.g., triangular grids [Lov73], or CWlog grids [PW95]
(that contain 2 i rows of length 2 i each). As the square grid already possesses a load within a constant
factor of the optimal, we do not pursue such constructions further.

Figure

1: Grid construction, k \Theta
Example 4.3 (Partition) Suppose that 4, is a partition of U where B
for all This choice of B could arise, for example, in a wide area network composed of
multiple local clusters, each containing some B i , and expresses the assumption that at any time,
at most one cluster is faulty. Then, any collection of nonempty sets -
can be
thought of as 'super-elements' in a universe of m, with a threshold assumption Therefore,
the following is a masking quorum system for B:
i2I
M1 is satisfied because the intersection of any two quorums contains elements from at least three
sets in B. M2 holds since there is no that intersects all quorums. Q is non-dominated iff
strategy that assigns equal probability to each quorum induces a
load of 1
2 e on the system regardless of the size of each -
again Corollary 4.2 implies
that this is the load of the system.
then a more efficient construction can be achieved by forming the grid
construction from Example 4.2 on the 'super elements' f -
achieving a load of 4
5 Variations
5.1 Dissemination quorum systems
As a special case of services which may employ quorums in a Byzantine environment, we now
consider applications in which the service is a repository for self-verifying information, i.e., information
that only clients can create and to which clients can detect any attempted modification
by a faulty server. A natural example is a database of public key certificates as found in many
public key distribution systems (e.g., [CCIT88, TA91, LABW92, Ken93]). A public key certificate
is a structure containing a name for a user and a public key, and represents the assertion that the
indicated public key can be used to authenticate messages from the indicated user. This structure
is digitally signed (e.g., [RSA78]) by a certification authority so that anyone with the public key
of this authority can verify this assertion and, providing it trusts the authority, use the indicated
public key to authenticate the indicated user. Due to this signature, it is not possible for a faulty
server to undetectably modify a certificate it stores. However, a faulty server can undetectably
suppress a change from propagating to clients, simply by ignoring an update from a certification
authority. This could have the effect, e.g., of suppressing the revocation of a key that has been
compromised.
As can be expected, the use of digital signatures to verify data improves the cost of accessing
replicated data. To support such a service, we employ a dissemination quorum system, which has
weaker requirements than masking quorums, but which nevertheless ensures that in applications
like those above, self-verifying writes will be propagated to all subsequent read operations despite
the arbitrary failure of some servers. To achieve this, it suffices for the intersection of every two
quorums to not be contained in any set of potentially faulty servers (so that a written value can
propagate to a read). And, supposing that operations are required to continue in the face of failures,
there should be quorums that a faulty set cannot disable.
Definition 5.1 A quorum system Q is a dissemination quorum system for a fail-prone system B if
the following properties are satisfied.
dissemination quorum system will suffice for propagating self-verifying information as in the
application described above. The write operation is implemented as described in Section 3, and
the read operation becomes:
Read: For a client to read a variable x, it queries each server in some quorum Q to obtain a set
of value/timestamp pairs . The client then discards those pairs that are
not verifiable (e.g., using an appropriate digital signature verification algorithm) and chooses
from the remaining pairs the pair !v; t? with the largest timestamp. v is the result of the
read operation.
It is important to note that timestamps must be included as part of the self-verifying infor-
mation, so they cannot be undetectably altered by faulty servers. In the case of the application
described above, existing standards for public key certificates (e.g., [CCIT88]) already require a
real-time timestamp in the certificate.
The following two lemmata prove correctness of the above protocol using dissemination quorum
systems:
Lemma 5.1 A read operation that is concurrent with no write operations returns the value written
by the last preceding write operation in some serialization of all preceding write operations.
Proof. Let W denote the set of write operations preceding the read. The read operation will return
the value written in the write operation in W with the highest timestamp, since the quorum in which
that write completed intersects the quorum in which the read occurs in at least one correct server.
So, it suffices to argue that there is a serialization of the writes in W in which this write operation
appears last, or in other words, that this write operation precedes no other write operation in W .
This is immediate, however, as if it did precede another write operation in W , that write operation
would have a higher timestamp. 2
In this case, we can also prove the following property.
Lemma 5.2 A read operation that is concurrent with one or more write operations returns either
the value written by the last preceding write operation in some serialization of all preceding write
operations, or any of the values being written in the concurrent write operations.
Proof. Due to the assumption of self-verifying data, the read operation must return a value written
in a preceding or concurrent write operation. If the read operation does not return a value written
in a concurrent write operation, then it must return the value written by the last preceding write
operation in some serialization of all preceding write operations, by an argument similar to that
for Lemma 4.1. 2
The above lemmata imply that the protocol above implements a single-writer single-reader
regular variable [Lam86]. Theorems analogous to the ones given for masking quorum systems
above are easily derived for dissemination quorums. Below, we list these results without proof.
Theorem 5.1 Let B be a fail-prone system for a universe U . Then there exists a dissemination
quorum system for B iff Bg is a dissemination quorum system for B.
Corollary 5.1 Let B be a fail-prone system for a universe U . Then there exists a dissemination
quorum system for B iff for all In particular, suppose that
fg. Then, there exists a dissemination quorum system for B iff n ? 3f .
Corollary 5.2 If Q is a dissemination quorum system over a universe of n elements, then L(Q) -
c(Q)
n g, and thus also
n .
Below, we provide several example constructions of dissemination quorum systems.
Example 5.1 (Threshold) Suppose that Note that this
corresponds to the usual threshold assumption that up to f servers may fail. Then, the quorum
system is a dissemination quorum system for B. D1 is satisfied
because any Q intersect in at least f +1 elements. D2 holds because d n+f+1e -
This system is non-dominated, and a strategy that assigns equal probability to each quorum induces
a load of 1
2 e on the system. By Corollary 5.2, this load is in fact the load of the system. 2
Example 5.2 (Grid) Let the universe be arranged in a grid as in Example 4.2 above, and let
n. Then, the quorum system
i2I
is a dissemination quorum system for B. D1 holds since every pair of quorums intersect in at least
holds since for any choice of f faulty elements in the grid, f
and a column remain available. A strategy that assigns equal probability to each quorum induces
a load of (f+2)
n , and by Corollary 5.2, this is the load of the system. 2
Example 5.3 (Partition) Suppose that partition of U as in example
4.3 above. Then, for any collection of nonempty sets -
the following is a
dissemination quorum system for B:
i2I
D1 is satisfied because the intersection of any two quorums contains elements from at least two sets
in B. D2 holds since there is no that intersects all quorums. Q is non-dominated iff j -
for all strategy that assigns equal probability to each quorum induces a load of
2k on the system regardless of the size of each -
5.2 implies that this is the
load of the system.
An improved dissemination quorum system is achieved by forming the grid construction of
example 5.2 above on the 'super-elements' f -
achieving a load of 3
2k . 2
5.2 Opaque masking quorum systems
Masking quorums impose a requirement that clients know the fail-prone system B, while there may
be reasons that clients should not be required to know this. First, it somewhat complicates the
client's read protocol. Second, by revealing the failure scenarios for which the system was designed,
the system also reveals the failure scenarios to which it is vulnerable, which could be exploited by
an attacker to guide an active attack against the system. By not revealing the fail-prone system to
clients, and indeed giving each client only a small fraction of the possible quorums, the system can
somewhat obscure (though perhaps not secure in any formal sense) the failure scenarios to which
it is vulnerable, especially in the absence of client collusion.
In this section we describe one way to modify the masking quorum definition of Section 4 to
be opaque, i.e., to eliminate the need for clients to know B. In the absence of the client knowing
B, the only method of which we are aware for the client to reduce a set of replies from servers to a
single reply from the service is via voting, i.e., choosing the reply that occurs most often. In order
for this reply to be the correct one, however, we must strengthen the requirements on our quorum
systems. Specifically, suppose that the variable x is written with quorum Q 1 , and that subsequently
x is read with quorum Q 2 . If B is the set of arbitrarily faulty servers, then is the
set of correct servers that possess the latest value for x (see Figure 2). In order for the client to
obtain this value by vote, this set must be larger than the set of faulty servers that are allowed
to respond, i.e., since these faulty servers can "team up" with the out-of-date
but correct servers in an effort to suppress the write operation, the number of correct, up-to-date
servers that reply must be no less than the number of faulty or out-of-date servers that can reply,
i.e.,
Definition 5.2 A quorum system Q is an opaque masking quorum system for a fail-prone system
B if the following properties are satisfied.
O2:

Figure

2: O1 and O2
Note that O1 admits the possibility of equality in size between (Q 1 "Q 2 )nB and (Q 2 "B)[(Q 2 nQ 1 ).
Equality is sufficient since, in the case that the faulty servers "team up" with the correct but out-
of-date servers in Q 2 , the value returned from (Q 1 " have a higher timestamp than
that returned by (Q Therefore, in the case of a tie, a reader can choose the value
with the higher timestamp. It is interesting to note that a strong inequality in O1 would permit a
correct implementation of a single-reader singer-writer safe variable that does not use timestamps
(by taking the majority value in a read operation).
It is not difficult to verify that an opaque masking quorum system enables a client to obtain
the correct answer from the service. The write operation is implemented as described in Section 1,
and the read operation becomes:
Read: For a client to read a variable x, it queries each server in some quorum Q to obtain a set
of value/timestamp pairs . The client chooses the pair !v; t? that appears
most often in A, and if there are multiple such values, the one with the highest timestamp.
The value v is the result of the read operation.
Opaque masking quorum systems, combined with the access protocol described previously, provide
the same semantics as regular masking quorum systems. The proof is almost identical to that for
regular masking quorums.
Lemma 5.3 A read operation that is concurrent with no write operations returns the value written
by the last preceding write operation in some serialization of all preceding write operations.
Below we give several examples of opaque masking quorum systems (or just "opaque quorum
systems") and describe their properties. When we refer to a system as non-dominated, we mean
within the class of opaque quorum systems for the given fail-prone system B.
Example 5.4 (Threshold) Suppose that
the quorum system is an opaque quorum system for B. O1 is
satisfied because for any Q
l n+4fm
l n\Gamma2fm
Similarly, O2 is satisfied because
O3 holds since d 2n+2fe - . Q is non-dominated, and a strategy that assigns equal probability
to each quorum induces a load of 1
d 2n+2fe on the system. Corollary 4.2 implies that this load is
in fact the load of the system. 2
The next theorem proves a resilience bound for opaque quorum systems.
Theorem 5.2 Suppose that fg. There exists an opaque quorum system for
Proof. That n - 5f is sufficient is already proved in Example 5.1 above. Now suppose that Q is
an opaque quorum system for B. Fix any Q exists by O3); note
that
exists by O3). Then and therefore there is some
such that B 2 '
By O1, (1) - (2), therefore and we have n - 5f . 2
Example 5.5 (Partition) Suppose that partition of U where B
for all i, 1 - i - 3k. Choose any collection of sets -
fixed constant c ? 0. Then,
i2I
is an opaque quorum system for B. O1 is satisfied since for any Q
Similarly, O2 is satisfied since
Finally, O3 is satisfied since no quorums. Q is non-dominated iff
A strategy that assigns equal probability to each quorum induces a load of 2k+1
on the system
regardless of the value of c, and again Corollary 4.2 (considering each -
as a single element of a
universe of size 3k) implies that this is the load of the system. 2
Unlike the case for regular masking quorum systems, an open problem is to find a technique for
testing whether, given a fail-prone system B, there exists an opaque quorum system for B (other
than an exhaustive search of all subsets of 2 U ).
In the constructions in Examples 5.3, 5.4 and 5.5 the resulting quorum systems exhibited loads
that at best were constant as a function of n. In the case of masking quorum systems, we were able
to exhibit quorum systems whose load decreased as a function of n, namely the grid quorums. A
natural question is whether there exists an opaque quorum system for any fail-prone system B that
has load that decreases as a function of n. In this section, we answer this question in the negative:
we show a lower bound of 1of the load for any opaque quorum system construction, regardless of
the fail-prone system.
Theorem 5.3 The load of any opaque quorum system is at least 1
.
Proof. O1 implies that for any Q
. Let
w be any strategy for the quorum system Q, and fix any Q 1 2 Q. Then, the total load induced by
w on the elements of Q 1 is:
l w
there must be some server in Q 1 that suffers a load at least 1
We now present a generic construction of an opaque quorum system for increasingly
large universe sizes n, that has a load that tends to 1
2 as n grows. 1 We give this construction
primarily to show that the lower bound of 1is tight; due to the requirement that
construction is not of practical use for coping with Byzantine failures.
Example 5.6 Suppose that the universe of servers is
f;g. Consider the n \Theta n Hadamard matrix H('), constructed recursively as
H(') has the property that H(')H(') I is the n \Theta n identity matrix. Using well-known
inductive arguments [Hal86, Ch. 14], it can be shown that (i) the first row and column
consist entirely of \Gamma1's, (ii) the i-th row and i-th column, for each i - 2, has 1's in n
positions (and
similarly for \Gamma1's), and (iii) any two rows (and any two columns)
in npositions, i.e., 1's in ncommon positions and \Gamma1's in ncommon positions.
We treat the rows of H(') as indicators of subsets of U . That is, let
be the set defined by the i-th row, 1 - i - n. Note that Q that u 1 is not included in
any Q i . We claim that the system is an opaque quorum system for B. Using
properties we have that jQ nfor each i - 2; that each u i , is in exactly
2 of the sets Q and that for any
4 . From these, the
O1 and O2 requirements can be quickly verified, and a load of nn\Gamma1 can be achieved, e.g., with a
strategy that assigns equal probability to each quorum. 2
6 Faulty clients
So far, we have been concerned with providing a consistent service to a set of correct clients. In this
section, we extend our treatment to address faulty clients in addition to faulty servers, as would
be required if servers are allowed to act as (or on behalf of) clients. Since updates may now be
generated by faulty clients, we can make no assumption of self-verifying data, and thus use masking
This construction slightly improves on a similar idea suggested to us by Andrew Odlyzko.
2 The more common form of Hadamard matrices is \Gamma1 times the form we use. However, the relevant characteristics
of Hadamard matrices are invariant to multiplication by \Gamma1.
quorum systems (Section 4) in our read and write protocols. We focus on ensuring the consistency
of the data stored at the replicated service as seen by correct clients only. Since a faulty client may
not complete a write operation at a quorum of servers, or may even write different values to different
servers, in this section we modify the write protocol to include an update protocol implemented
by the servers that prevents clients from leaving the service in an inconsistent state. This update
protocol could be implemented using well-known agreement protocols (e.g., [LSP82, BT85]), but
only if the given fail-prone system B has the property that each B 2 B is of size less than jU j=3,
and only by involving all of the servers in the system. We describe two protocols that are correct
for any fail-prone system B for which a masking quorum exists, and that involve only a quorum
of correct servers to complete an update operation. While we do not explicitly treat load in this
section, this latter property is essential for the load measure that we have defined to be useful.
The write protocol
This section describes the protocol by which clients write the variable x replicated at each server.
We replace the write operation of Section 3 by the following procedure:
Write: For a client c to write the value v, it queries each server in some quorum Q to obtain a
set of value/timestamp pairs chooses a timestamp t 2 T c greater than the
highest timestamp value in A and greater than any timestamp it has chosen in the past; and
performs InitiateUpdate(Q, v, t).
Note that writing the pair !v; t? to the quorum Q is performed by executing the operation
InitiateUpdate(Q; v; t). Servers execute corresponding events DeliverUpdate(c; v; t) where c is a
client. If a correct server executes DeliverUpdate(c; v; t), and if t 2 T c and is greater than the
timestamp currently stored with the variable, then the server updates the value of the variable and
its timestamp to v and t, respectively. Regardless of whether it updates the variable, it sends an
acknowledgment message to c.
Correctness of this protocol depends on the following relationships among InitiateUpdate executions
at clients and DeliverUpdate events at servers. How to implement the InitiateUpdate and
DeliverUpdate primitives to satisfy these relationships is the topic of this section.
If c is correct, then a correct server executes DeliverUpdate(c; v; t) only if c executed
Agreement: If a correct server executes DeliverUpdate(c; v; t) and a correct server executes
Propagation: If a correct server executes DeliverUpdate(c; v; t), then eventually there exists a
quorum that every correct server in Q executes DeliverUpdate(c; v; t).
Validity: If a correct client c executes InitiateUpdate(Q; v; t) and all servers in Q are correct, then
eventually a correct server executes DeliverUpdate(c; v; t).
Note that by Validity, if a correct client executes InitiateUpdate(Q; v; t) but Q contains a faulty
server, then there is no guarantee that DeliverUpdate(c; v; t) will occur at any correct server; i.e.,
the write operation may have no effect. A correct server acknowledges each DeliverUpdate(c; v; t)
execution as described above to inform c that DeliverUpdate(c; v; t) was indeed executed. If the
client receives acknowledgments from a set B + of servers, such that 8B then it is
certain that its write will be applied at all correct servers in some quorum Q (by Propagation).
If the client receives acknowledgements from no such set B + of servers, then it must attempt the
operation again with a different quorum. By M2, some quorum with correct servers exists at
any moment, and thus by repeatedly trying, a client can eventually make progress. In some cases,
the client can achieve progress by incrementally accessing servers until it obtains acknowledgements
from a quorum of them.
In order to argue correctness for this protocol, we have to adapt the definition of operation
precedence to allow for the behavior of a faulty client. The reason is that it is unclear how to define
when an operation at a faulty client starts or, in the case of a read, when it terminates, as the client
can behave outside the specification of any protocol. We now simply say that a write operation that
writes v with timestamp t 2 T c terminates when all correct servers in some quorum have executed
any write operation and op 2 be any operation (read or write)
executed by a correct client. We say that op 1 precedes op 2 if and only if op 1 terminates before
starts (in real time, at the correct client); otherwise, and if op 2 does not precede op 1 and op 1
eventually terminates, then op 1 is concurrent with op 2 . Note that by this definition, no operations
precede an operation involving a faulty client, and every operation by a faulty client either precedes
or is concurrent with every other operation. Given this change in definition, a proof very similar
to that of Lemma 4.1 suffices to prove the following:
Lemma 6.1 A correct process' read operation that is concurrent with no write operations returns
the value written by the last preceding write operation in some serialization of all preceding write
operations.
The update operation: without signatures
The remaining protocol to describe is the update protocol for masking quorum systems that satisfies
Integrity, Agreement, Propagation, and Validity. We first present an update protocol that does not
use digital signatures. The protocol is shown in Figure 3.
Lemma 6.2(Integrity) If c is correct, then a correct server executes DeliverUpdate(c; v; t) only if
c executed InitiateUpdate(Q; v; t) for some Q.
Proof. The first !ready; Q; c; v; t? message from a correct server is sent only after it receives
!echo; Q; c; v; t? from each member of Q. Moreover, a correct member sends !echo; Q; c; v; t? only if
it receives !update; Q; v; t? for some Q from c over an authenticated channel, i.e., only if c executed
InitiateUpdate(Q; v; t). 2
Lemma 6.3(Agreement) If a correct server executes DeliverUpdate(c; v; t) and a correct server
executes
Proof. As argued in the previous lemma, for a correct server to execute DeliverUpdate(c; v;
must have been sent by all servers in Q. Similarly, !echo; Q must have
been sent by all servers in Q 0 . Since every two quorums intersect in (at least) one correct member,
and since any correct server sends !echo;  ; c; -v; t? for at most one value - v, v must be identical to
Lemma 6.4 If Q is a masking quorum system over a universe U with respect to a fail-prone system
B, then 8Q 2 Q
1. If a client executes InitiateUpdate(Q; v; t), then it sends !update; Q; v; t? to each member of
Q.
2. If a server receives !update; Q; v; t? from a client c, and if the server has not previously received
from c a message !update; Q t, then the server
sends !echo; Q; c; v; t? to each member of Q.
3. If a server receives identical echo messages !echo; Q; c; v; t? from every server in Q, then it
sends !ready; Q; c; v; t? to each member of Q.
4. If a server receives identical ready messages !ready; Q; c; v; t? from a set B + of servers, such
B, then it sends !ready; Q; c; v; t? to every member of Q if it has not
done so already.
5. If a server receives identical ready messages !ready; Q; c; v; t? from a set Q \Gamma of servers, such
that for some B 2 B,

Figure

3: An update protocol that does not use signatures
Proof. Assume otherwise for a contradiction, i.e., that there is a
that . By M2, there exists Q
thus contradicting M1. 2
Lemma 6.5(Propagation) If a correct server executes DeliverUpdate(c; v; t), then eventually there
exists a quorum Q 2 Q such that every correct server in Q executes DeliverUpdate(c; v; t).
Proof. According to the protocol, the correct server that executed DeliverUpdate(c; v; t) received
a message !ready; Q; c; v; t? from each server in
some all the members in are correct, every correct member of Q receives
t? from each of the members of (by
Lemma 6.4), the ready messages from B cause each correct member of Q to send such a ready
message. Consequently, DeliverUpdate(c; v; t) is executed by all of the correct members of Q. 2
Lemma 6.6(Validity) If a correct client c executes InitiateUpdate(Q; v; t) and all servers in Q are
correct, then eventually a correct server executes DeliverUpdate(c; v; t).
Proof. Since both the client and all of the members of Q are correct, !update; Q; v; t? will be received
and echoed by every member in Q. Consequently, all the servers in Q will send !ready; Q; c; v; t?
messages to the members of Q, and will eventually execute DeliverUpdate(c; v; t). 2
The update operation: with signatures
The update protocol that we describe in this section requires that each server be able to digitally
sign a message so that any party can reliably authenticate the message as having originated from
that server, even if the message is received only via an (untrusted) intermediary. Digital signature
algorithms are well-known (e.g., [RSA78]). In the remainder of this section, we use m u to denote
the message m signed by server u. The use of digital signatures results in an Update protocol
that exchanges significantly less messages than the protocol in Figure 3. This protocol is shown in

Figure

4.
1. If a client executes InitiateUpdate(Q; v; t), then it sends !update; Q; v; t? to each member of
Q.
2. If a server u receives !update; Q; v; t? from a client c, and if u has not previously received
from c a message !update; Q
!echo; Q; c; v; t? u to c.
3. If a client c receives !echo; Q; c; v; t? u from every member of Q, then it sends
f!echo; Q; c; v; t? u g u2Q to each member of Q.
4. If a server u 2 Q receives f!echo; Q; c; v; t? u g u2Q , then it executes DeliverUpdate(c; v; t), and
sends f!echo; Q; c; v; t? u g u2Q to each member of Q if it has not already done so.

Figure

4: A update protocol that uses signatures
Lemma 6.7(Integrity) If c is correct, then a correct server executes DeliverUpdate(c; v; t) only if
c executed InitiateUpdate(Q; v; t) for some Q.
Proof. For a correct server to execute DeliverUpdate(c; v; t), it must receive f!echo; Q; c; v; t? u g u2Q
for some quorum Q. But each correct server u 2 Q sends !echo; Q; c; v; t? u only after receiving
!update; Q; v; t? from c (on an authenticated channel), i.e., only if c executed InitiateUpdate(Q; v; t).Lemma 6.8(Agreement) If a correct server executes DeliverUpdate(c; v; t) and a correct server
executes
Proof. As argued in the previous lemma, for a correct server to execute DeliverUpdate(c; v;
must have been sent by all u 2 Q. Similarly, !echo; Q must have been
sent by all u 2 Q 0 . Since every two quorums intersect in (at least) one correct member, and since
any correct server u sends !echo;  ; c; -v; t? u for at most one value - v, v must be identical to v 0 . 2
Lemma 6.9(Propagation) If a correct server executes DeliverUpdate(c; v; t), then eventually there
exists a quorum Q 2 Q such that every correct server in Q executes DeliverUpdate(c; v; t).
Proof. The correct server that executed DeliverUpdate(c; v; t) received f!echo; Q; c; v; t? u g u2Q for
some quorum Q. By forwarding this to all servers in Q in step 4 of the protocol, it will cause all
correct servers in Q to execute DeliverUpdate(c; v; t). 2
Lemma 6.10(Validity) If a correct client c executes InitiateUpdate(Q; v; t) and all servers in Q
are correct, then eventually a correct server executes DeliverUpdate(c; v; t).
Proof. Since both the client and all of the members of Q are correct, !update; Q; v; t? will be
received and echoed by every member in Q, and the client will forward these echos to all members
of Q. Hence each member of Q will execute DeliverUpdate(c; v; t). 2
Conclusions
The literature contains an abundance of protocols that use quorums for accessing replicated data.
This approach is appealing for constructing replicated services as it allows for increasing the availability
and efficiency of the service while maintaining its consistency. Our work extends this successful
approach to environments where both the servers and the clients of a service may deviate
from their prescribed behavior in arbitrary ways. We introduced a new class of quorum systems,
namely masking quorum systems, and devised protocols that use these quorums to enhance the
availability of systems prone to Byzantine failures. We also explored two variations of our quorum
systems, namely dissemination and opaque masking quorums, and for all of these classes of
quorums we provided various constructions and analyzed the load they impose on the system.
Our work leaves a number of intriguing open challenges and directions for future work. One is to
characterize the average performance of our quorum constructions and their load in less-than-ideal
scenarios, e.g., when failures occur. More generally, in this work we described only quorum systems
that are uniform, in the sense that any quorum is possible for both read and write operations. In
practice it may be beneficial to employ quorum systems with distinguished read quorums and write
quorums, with consistency requirements imposed only between pairs consisting of at least one write
quorum. Although this does not seem to improve our lower bounds on the overall load that can be
achieved, it may allow greater flexibility in trading between the availability of reads and writes.

Acknowledgments

We are grateful to Andrew Odlyzko for suggesting the use of Hadamard matrices to construct
opaque masking quorum systems with an asymptotic load of 1. We also thank Yehuda Afek and
Michael Merritt for helpful discussions, and Rebecca Wright for many helpful comments on earlier
versions of this paper. An insightful comment by Rida Bazzi led to a substantial improvement over
a previous version of this paper.



--R

Atomic snapshots of shared memory.
A bounded first-in first-enabled-solution to the l-exclusion problem
Integrating security with fault-tolerant distributed databases
An efficient and fault-tolerant solution for distributed mutual exclusion
Composite registers.
Sharing Memory Robustly in Message-Passing Systems
Concurrency control and recovery in database systems.
Asynchronous consensus and broadcast protocols.
The grid protocol: A high performance scheme for maintaining replicated data.

Toward a non-atomic era: l-exclusion as a test case
Bounded concurrent time-stamp systems are constructible
Maintaining availability in partitioned replicated databases.
How to assign votes in a distributed system.
Weighted voting for replicated data.

A quorum-consensus replication method for abstract data types
How to make replicated data secure.
Bounded time-stamps
Internet privacy enhanced mail.
Hierarchical quorum consensus: A new algorithm for managing replicated data.
Optimal multi-write multi-reader atomic register
The Byzantine generals problem.
Authentication in distributed systems: Theory and practice.
On interprocess communication (part II: algorithms).
Coverings and colorings of hypergraphs.
How to share concurrent wait-free variables
A p n algorithm for mutual exclusion in decentralized systems.
Tolerating failures of continuous-valued sensors

Storage efficient and secure replicated distributed databases.
The load
Access control and signatures via quorum secret sharing.
Crumbling walls: A class of high availability quorum systems.
Efficient dispersal of information for security
Secure agreement protocols: Reliable and atomic group multicast in Rampart.
Distributing trust with the Rampart toolkit.
How to securely replicate services.
A method for obtaining digital signatures and public-key cryp- tosystems
How to share a secret.
Implementing fault-tolerant services using the state machine approach: A tutorial
SPX: Global authentication using public key certificates.
A majority consensus approach to concurrency control for multiple copy databases.
Randomized Byzantine agreement.
--TR
How to assign votes in a distributed system
A quorum-consensus replication method for abstract data types
Efficient dispersal of information for security, load balancing, and fault tolerance
Toward a non-atomic era: l-exclusion as a test case
Maintaining availability in partitioned replicated databases
Bounded concurrrent time-stamp systems are constructible
Integrating security with fault-tolerant distributed databases
An efficient and fault-tolerant solution for distributed mutual exclusion
A bound first-in, first-enabled solution to the 1-exclusion problem
Optimal multi-writer multi-reader atomic register
Authentication in distributed systems
Atomic snapshots of shared memory
A <inline-equation> <f> <rad><rcd>N</rcd></rad></f> </inline-equation> algorithm for mutual exclusion in decentralized systems
How to share concurrent wait-free variables
Access control and signatures via quorum secret sharing
Byzantine quorum systems
The load and availability of Byzantine quorum systems
Synchronous Byzantine quorum systems
Probabilistic quorum systems
Probabilistic Byzantine quorum systems
The Load, Capacity, and Availability of Quorum Systems
Combinatorial theory (2nd ed.)
A Majority consensus approach to concurrency control for multiple copy databases
How to share a secret
A method for obtaining digital signatures and public-key cryptosystems
Storage Efficient and Secure Replicated Distributed Databases
The Grid Protocol
How to Make Replicated Data Secure
Weighted voting for replicated data
Survivable Consensus Objects
Secure and Scalable Replication in Phalanx

--CTR
Evelyn Pierce , Lorenzo Alvisi, A framework for semantic reasoning about Byzantine quorum systems, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.317-319, August 2001, Newport, Rhode Island, United States
Rodrigo Rodrigues , Barbara Liskov, Brief announcement: reconfigurable byzantine-fault-tolerant atomic memory, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Tatsuhiro Tsuchiya , Tohru Kikuno, Byzantine quorum systems with maximum availabililty, Information Processing Letters, v.83 n.2, p.71-77, 31 July 2002
Yuan-Bo Guo , Jian-Feng Ma, Practical secret sharing scheme realizing generalized adversary structure, Journal of Computer Science and Technology, v.19 n.4, p.564-569, July 2004
Ittai Abraham , Gregory Chockler , Idit Keidar , Dahlia Malkhi, Wait-free regular storage from Byzantine components, Information Processing Letters, v.101 n.2, p.60-65, January, 2007
Rida A. Bazzi, Access cost for asynchronous Byzantine quorum systems, Distributed Computing, v.14 n.1, p.41-48, January 2001
Dahlia Malkhi , Michael Merritt , Ohad Rodeh, Secure reliable multicast protocols in a WAN, Distributed Computing, v.13 n.1, p.19-28, January 2000
Rida A. Bazzi, Synchronous Byzantine quorum systems, Distributed Computing, v.13 n.1, p.45-52, January 2000
Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Fred B. Schneider , Lidong Zhou, Implementing Trustworthy Services Using Replicated State Machines, IEEE Security and Privacy, v.3 n.5, p.34-43, September 2005
Alysson Neves Bessani , Joni da Silva Fraga , Lau Cheuk Lung, BTS: a Byzantine fault-tolerant tuple space, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Lorenzo Alvisi , Dahlia Malkhi , Evelyn Pierce , Michael K. Reiter, Fault Detection for Byzantine Quorum Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.996-1007, September 2001
Rachid Guerraoui , Marko Vukoli, How fast can a very robust read be?, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Dahlia Malkhi , Yishay Mansour , Michael K. Reiter, Diffusion without false rumors: on propagating updates in a Byzantine environment, Theoretical Computer Science, v.299 n.1-3, p.289-306,
Bryan Parno , Mema Roussopoulos, Defending a P2P Digital Preservation System, IEEE Transactions on Dependable and Secure Computing, v.1 n.4, p.209-222, October 2004
Hyunyoung Lee , Jennifer L. Welch, Randomized registers and iterative algorithms, Distributed Computing, v.17 n.3, p.209-221, March 2005
Petros Maniatis , David S. H. Rosenthal , Mema Roussopoulos , Mary Baker , TJ Giuli , Yanto Muliadi, Preserving peer replicas by rate-limited sampled voting, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, APSS: proactive secret sharing in asynchronous systems, ACM Transactions on Information and System Security (TISSEC), v.8 n.3, p.259-286, August 2005
Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination  in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000
Ittai Abraham , Dahlia Malkhi, Probabilistic quorums for dynamic systems, Distributed Computing, v.18 n.2, p.113-124, December 2005
Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005
Michael A. Marsh , Fred B. Schneider, CODEX: A Robust and Secure Secret Distribution System, IEEE Transactions on Dependable and Secure Computing, v.1 n.1, p.34-47, January 2004
T. J. Giuli , Petros Maniatis , Mary Baker , David S. H. Rosenthal , Mema Roussopoulos, Attrition defenses for a peer-to-peer digital preservation system, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.12-12, April 10-15, 2005, Anaheim, CA
Miguel Correia , Nuno Ferreira Neves , Lau Cheuk Lung , Paulo Verssimo, Worm-IT - A wormhole-based intrusion-tolerant group communication system, Journal of Systems and Software, v.80 n.2, p.178-197, February, 2007
Dahlia Malkhi , Michael K. Reiter , Avishai Wool , Rebecca N. Wright, Probabilistic quorum systems, Information and Computation, v.170 n.2, p.184-206, November 1, 2001
Meng Yu , Peng Liu , Wanyu Zang, Specifying and using intrusion masking models to process distributed operations, Journal of Computer Security, v.13 n.4, p.623-658, July 2005
Jian Yin , Jean-Philippe Martin , Arun Venkataramani , Lorenzo Alvisi , Mike Dahlin, Separating agreement from execution for byzantine fault tolerant services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002
Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002
byzantine failures;quorum systems;replication;fault tolerance