Fault Detection for Byzantine Quorum Systems.
AbstractIn this paper, we explore techniques to detect Byzantine server failures in asynchronous replicated data services. Our goal is to detect arbitrary failures of data servers in a system where each client accesses the replicated data at only a subset (quorum) of servers in each operation. In such a system, some correct servers can be out-of-date after a write and can therefore, return values other than the most up-to-date value in response to a client's read request, thus complicating the task of determining the number of faulty servers in the system at any point in time. We initiate the study of detecting server failures in this context, and propose two statistical approaches for estimating the risk posed by faulty servers based on responses to read requests.
Introduction
Data replication is a well-known means of protecting against data unavailability
or corruption in the face of data server failures. When servers can suffer Byzantine
(i.e., arbitrary) failures, the foremost approach for protecting data is via state
machine replication [Sch90], in which every correct server receives and processes
every request in the same order, thereby producing the same output for each re-
quest. If the client then accepts a value returned by at least t
to t arbitrary server failures can be masked. Numerous systems have been built to
support this approach (e.g., [PG89, SESTT92, Rei94, KMM98]).
To improve the efficiency and availability of data access while still protecting the
integrity of replicated data, the use of quorum systems has been proposed. Quorum
preprint of paper to appear in Seventh IFIP International Working Conference on Dependable
Computing for Critical Applications (DCCA-7) January, 1999, San Jose, California
y Department of Computer Science, University of Texas, Austin, Texas;
lorenzo@cs.utexas.edu. This work was funded in part by a NSF CAREER award (CCR-
9734185), a DARPA/SPAWAR grant number N66001-98-8911 and a NSF CISE grant (CDA-
z AT&T Labs-Research, Florham Park, New Jersey; dalia@research.att.com
x Department of Computer Science, University of Texas, Austin, Texas; tumlin@cs.utexas.edu
- Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey; reiter@research.bell-
labs.com
Alvisi, Malkhi, Pierce, Reiter
systems are a family of protocols that allow reads and updates of replicated data
to be performed at only a subset (quorum) of the servers. In a t-masking quorum
system, the quorums of servers are defined such that any two quorums intersect in
at least 2t In a system with a maximum of t faulty
servers, if each read and write operation is performed at a quorum, then the quorum
used in a read operation will intersect the quorum used in the last preceding write
operation in at least t+1 correct servers. With appropriate read and write protocols,
this intersection condition ensures that the client is able to identify the correct, up-
to-date data [MR97a].
A difficulty of using quorum systems for Byzantine fault tolerance is that detecting
responsive but faulty servers is hard. In state machine replication, any server
response that disagrees with the response of the majority immediately exposes the
failure of the disagreeing server to the client. This property is lost, however, with
quorum systems: because some servers remain out of date after any given write, a
contrary response from a server in a read operation does not necessarily suggest the
server's failure. Therefore, we must design specific mechanisms to monitor the existence
of faults in a quorum-replicated system, e.g., to detect whether the number
of failures is approaching t.
In this paper, we initiate the study of Byzantine fault detection methods for quorum
systems by proposing two statistical techniques for estimating the number of
server failures in a service replicated using a t-masking quorum system. Both of
our methods estimate the total number of faulty servers from responses to a client's
read requests executed at a quorum of servers, and are most readily applicable to
the threshold quorum construction of [MR97a], in which a quorum is defined as any
set of size d n+2t+1
e. The first method has the advantage of requiring essentially no
change to the read and write protocols proposed in [MR97a]. The second method
does require an alteration of the read and write protocols, but has the advantages
of improved accuracy and specific identification of a subset of the faulty servers.
Furthermore, the fault identification protocol of the second method is applicable
without alteration to all types of t-masking quorum systems, and indeed to other
types of Byzantine quorum systems as proposed in [MR97a].
Both methods set an alarm line t a ! t and issue a warning whenever the number
of server failures exceeds t a . We show how the system can use information from
each read operation to statistically test the hypothesis that the actual number of
faults f in the system is at most t a . As we will show, if t a is correctly selected and
read operations are frequent, both methods can be expected to issue warnings in a
timely fashion, i.e., while it is still the case that f ! t. The service can then be
repaired (or at least disabled) before the integrity of the data set is compromised.
As an initial investigation into the statistical monitoring of replicated data, this
paper adopts a number of simplifying assumptions. First, we perform our statistical
analysis in the context of read operations that are concurrent with no write oper-
ations, as observing partially completed writes during a read substantially complicates
the task of inferring server failures. Second, we assume that clients are
correct; distinguishing a faulty server from a server into which a faulty client has
Fault Detection for Byzantine Quorum Systems
written incorrect data raises issues that we do not consider here. Third, we restrict
our attention to techniques that modify the read and write protocols only minimally
or not at all and that exploit data gathered from a single read only, without aggregating
data across multiple reads. (As we will show in this paper, a surprising
amount of information can be obtained without such aggregation.) Each of these
assumptions represents an area for possible future research.
The goal of our work is substantially different from that of various recent works
that have adapted failure detectors [CT96] to solve consensus in distributed systems
that can suffer Byzantine failures [MR97b, DS97, KMM97]. These works focus on
the specification of abstract failure detectors that enable consensus to be solved.
Our goal here is to develop techniques for detecting Byzantine failures specifically
in the context of data replicated using quorum systems, without regard to abstract
failure detector specifications or the consensus problem. Lin et al. [LRM98] analyze
the process of gradual infection of a system by malicious entities. Their analysis
attempts to project when failures exceed certain thresholds by extrapolating from
observed failures onto the future, on the basis of certain a priori assumptions about
the communication patterns of processes and the infection rate of the system. Our
methods do not depend on these assumptions, as they do not address the propagation
of failures in the system; rather, they attempt to measure the current number of
failures at any point in time.
To summarize, the contributions of this paper are twofold: we initiate the direction
of fault monitoring and detection in the context of Byzantine quorum sys-
tems; and we propose two statistical techniques for performing this detection for
t-masking quorum systems under the conditions described above. The rest of this
paper is organized as follows. In Section 2 we describe our system model and
necessary background. In Sections 3-4 we present and analyze our two statistical
methods using exact formulae for alarm line placement in relatively small systems.
In Section 5 we present an asymptotic analysis for estimating appropriate alarm line
placement in larger systems for both methods. We conclude in Section 6.
Preliminaries
2.1 System model
Our system model is based on a universe U of n data servers. A correct server is
one that behaves according to its specification, whereas a faulty server deviates from
its specification arbitrarily (Byzantine failure). We denote the maximum allowable
number of server failures for the system by t, and the actual number of faulty servers
in the system at a particular moment by f . Because our goal in this paper is to
detect faulty servers, we stipulate that a faulty server does in fact deviate from its
I/O specification, i.e., it returns something other than what its specification would
dictate (or it returns nothing, though unresponsive servers are ignored in this paper
and are not the target of our detection methods). It is hardly fruitful to attempt to
detect "faulty" servers whose visible behavior is consistent with correct execution.
Alvisi, Malkhi, Pierce, Reiter
Our system model also includes some number of clients, which we assume to be
correct. Clients communicate with servers over point-to-point channels. Channels
are reliable, in the sense that a message sent between a client and a correct server
is eventually received by its destination. In addition, a client can authenticate the
channel to a correct server; i.e., if the client receives a message from a correct
server, then that server actually sent it.
2.2 Masking quorum systems
We assume that each server holds a copy of some replicated variable Z , on
which clients can execute write and read operations to change or observe its value,
respectively. The protocols for writing and reading Z employ a t-masking quorum
system [MR97a, MRW97], i.e., a set of subsets of servers Q ' 2 U such that
Intuitively, if each read and write is performed
at a quorum of servers, then the use of a t-masking quorum system ensures that a
read quorum Q 2 intersects the last write quorum Q 1 in at least t
which suffices to enable the reader to determine the last written value. Specifically,
we base our methods on threshold masking quorum systems [MR97a], defined by
i.e., the quorums are all sets of servers of size
d n+2t+1
2 e. These systems are easily seen to have the t-masking property above.
We consider the following protocols for accessing the replicated variable Z ,
which were shown in [MR97a] to give Z the semantics of a safe variable [Lam86].
Each server u maintains a timestamp T u with its copy Z u of the variable Z . A
client writes the timestamp when it writes the variable. These 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 .
Client operations proceed as follows.
Write: For a client c to write the value v to Z , it queries each server in some
quorum Q to obtain a set of value/timestamp pairs
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 Z u and T u at each server u in
some quorum Q 0
to v and T , respectively.
Read: For a client to read a variable Z , it queries each server in some quorum Q to
obtain a set of value/timestamp pairs From among all pairs
returned by at least t servers in Q, the client chooses the pair !v; T? with the
highest timestamp T , and then returns v as the result of the read operation. If there
is no pair returned by at least t servers, the result of the read operation is ? (a
null value).
In a write operation, each server u updates Z u and T u to the received values !v; T?
only if T is greater than the present value of T u ; this convention guarantees the seri-
Fault Detection for Byzantine Quorum Systems
alizability of concurrent writes. As mentioned in Section 1 we consider only reads
that are not concurrent with writes. In this case, the read operation will never return
? (provided that the assumed maximum number of failures t is not exceeded).
2.3 Statistical building blocks
The primary goal of this paper is to draw conclusions about the number f of
faulty servers in the system, specifically whether f exceeds a selected alarm threshold
t a , where t, using the responses obtained in the read protocol of
the previous subsection. To do this, we make extensive use of a statistical technique
called hypothesis testing. To use this technique, we establish two hypotheses
about our universe of servers. The first of these is an experimental hypothesis HE
that represents a condition to be tested for, e.g., that f exceeds the alarm threshold
t a , and the second is a null hypothesis H 0 complementing it. The idea behind
hypothesis testing is to examine experimental results (in our case, read operations)
for conditions that suggest the truth of the experimental hypothesis, i.e., conditions
that would be "highly unlikely" if the null hypothesis were true. We define "highly
unlikely" by choosing a rejection level identifying a corresponding
region of rejection for H 0 , where the region of rejection is the maximal set of
possible results that suggest the truth of HE (and thus the falsity of H 0 ) and whose
total probability given H 0 is at most ff. For the purposes of our work, HE will be
. (Note that although these hypotheses are not
strictly complementary, the region of rejection for H 0 encompasses that of every
a , where
therefore the rejection level of the truly
complementary hypothesis f - t a is bounded by that of H 0 . This treatment of the
null hypothesis is a standard statistical procedure.)
In this paper we will typically choose t a to be strictly less than the maximum
assumed number t of failures in the system, for the reason
that it is of little use to detect a dangerous condition after the integrity of the
data has been compromised. The "safest" value for t a is 0, but a higher value
may be desirable if small numbers of faults are common and countermeasures are
expensive.
In order for our statistical calculations to be valid, we must be able to treat individual
quorums and the intersection between any two quorums as random samples
of the universe of servers. Given our focus on a quorum system consisting of all
sets of size d n+2t+1
2 e, this can be accomplished by choosing quorums in such a way
that each quorum (not containing unresponsive servers) is approximately equally
likely to be queried for any given operation.
As in any statistical method, there is some possibility of false positives (i.e.,
alarms sent when the fault level remains below t a ) and false negatives (failure to
detect a dangerous fault level before the threshold is exceeded). As we will show,
however, the former risk can be kept to a reasonable minimum, while the latter can
be made essentially negligible. 1
1 Except in catastrophically unreliable systems. Neither our method nor any other of which we
Alvisi, Malkhi, Pierce, Reiter
3 Diagnosis using justifying sets
Our first method of fault detection for threshold quorum systems uses the read
and write protocols described in Section 2.2. As the random variable for our statistical
analysis, we use the size of the justifying set for a read operation, which is
the set of servers that return the value/timestamp pair !v; T? chosen by the client
in the read operation. The size of the justifying set is at least 2t there are no
faulty servers, but can be as small as t. The justifying set may be as
large as d n+2t+1
e in the case where the read quorum is the same as the quorum used
in the last completed write operation.
Suppose that a read operation is performed on the system, and that the size of
the justifying set for that read operation is x. We would like to discover whether
this evidence supports the hypothesis that the number of faults f in the system
exceeds some value t a , where t a ! t. We do so using a formula for the probability
distribution for justifying set sizes; this formula is derived as follows.
Suppose we have a system of n servers, with a quorum size of q. Given f faulty
servers in the system, the probability of exactly j failures in the read quorum can
be expressed by a hypergeometric distribution as follows:
q\Gammaj
Given that the number of failures in the read quorum is j, the probability that there
are exactly x correct servers in the intersection between the read quorum and the
previous write quorum is formulated as follows: the number of ways of choosing x
correct servers from the read quorum is
x
, and the number of possible previous
write quorums that intersect the read quorum in exactly those correct servers (and
some number of incorrect ones) is
. The probability that the previous write
quorum intersects the read quorum in exactly this way is therefore:
x
To get the overall probability that there are exactly x correct servers in the intersection
between the read and most recent write quorums, i.e., that the justifying
set size (size) is x, we multiply the conditional probability given j failures in the
read quorum by the probability of exactly j failures in the read quorum, and sum
the result for
f
x
q\Gammaj
(1)
are aware will protect against sudden near-simultaneous Byzantine failures in a sufficiently large
number (e.g., greater than t) of servers.
Fault Detection for Byzantine Quorum Systems
This formula expresses the probability that a particular read operation in a t-masking
quorum system will have a justifying set size of x given the presence of f faults.
For a given rejection level ff, then, the region of rejection for the null hypothesis
a is defined as x - highreject, where highreject is the maximum value such
highreject X
t a
x
ji t a
ji n\Gammat a
q\Gammaj
The left-hand expression above represents the significance level of the test, i.e.,
the probability of a false positive (false alarm).
If there are in fact failures in the system, the probability of detecting this
condition on a single read is:
highreject X
x
q\Gammaj
If we denote this value by fl, then the probability that k consecutive reads fail to
detect the condition is As shown in the following examples, k need not
be very large for this probability to become negligible.
Example 1: Consider a system of
fault tolerance threshold In order to test whether there are any faults in the
system, we set t a = 0, so that the null hypothesis H 0 is and the experimental
hypothesis HE is f ? 0. Plugging these numbers into (1) over the full range of
x yields the results in Table 1. For all other values of x not shown in Table 1, the
probability of a justifying set of size x given
0:071, the region of rejection for defined as x - 53; if a read operation
has a justifying set of size 53 or less, the client rejects the null hypothesis and
concludes that there are faults in the system. This test has a significance level of
that is, there is a probability of 0.019 that the client will detect faults when
there are none. (If this level of risk is unacceptable for a particular system, ff can
be set to a lower value, thus creating a smaller region of rejection.)
Suppose that there are actually f failures in the system. The probability that this
experiment will detect the presence of failures during any given read is:X
x=26
f
x
f
101\Gammaf

Table

shows these values for 1 - f - 20.
Although the probability of detecting faults during a given read in this system is
relatively low for very small values of f , it would appear that this test is reasonably
Alvisi, Malkhi, Pierce, Reiter
x
54 .051857 67 9:03 \Theta 10 \Gamma07

Table

1: Probability distribution on justifying set sizes for Example 1
9 .739333 19 .997720

Table

2: Probability of detecting f ? 0 in Example 1
Fault Detection for Byzantine Quorum Systems
9 .130284

Table

3: Probability of detecting f ? 5 in Example 2
powerful. Even for fault levels as low as 4 or 5, a client can reasonably expect
to detect the presence of failures within a very few reads; e.g., if then the
probability of detecting that f ? t a in only 6 reads is already
:921. As the fault levels rise, the probability of such detection within a single read
approaches near-certainty.
Example 2: Consider a much smaller system consisting of
a quorum size q = 46 and a fault tolerance threshold Furthermore, suppose
that the administrator of this system has decided that no action is called for if only
a few failures occur, so that t a is set at 5 rather than 0. Given 0:05, the region
of rejection for the null hypothesis H a is x - 27. The probabilities
of detecting this condition for actual values of f between 8 and 12 inclusive are
shown in Table 3.
As one might expect, error conditions are more difficult to detect when they are
more narrowly defined, as the contrast between examples 1 and 2 shows. Even in
the latter experiment, however, a client can reasonably expect to detect a serious but
non-fatal error condition within a small number of reads. For the probability
that the alarm is triggered within six read operations is
approximately 96.5 percent. The probability that it is triggered within ten reads
is over 99.6 percent. We can therefore reasonably consider this technique to be a
useful diagnostic in systems where read operations are significantly more frequent
than server failures, particularly if the systems are relatively large.
While the ability to detect faulty servers in threshold quorum systems is a step
forward, this method leaves something to be desired. It gives little indication of
the specific number of faults that have occurred and provides little information toward
identifying which servers are faulty. In the next section we present another
diagnostic method that addresses both these needs.
4 Diagnosis using quorum markers
The diagnostic method presented in this section has two distinct functions. First,
it uses a technique similar to that of the previous section to estimate the fault distribution
over the whole system, but with greater precision. Second, it pinpoints
Alvisi, Malkhi, Pierce, Reiter
specific servers that exhibit detectably faulty behavior during a given read. The
diagnostic operates on an enhanced version of the read/write protocol for masking
quorum systems: the write marker protocol, described below.
4.1 The write marker protocol
The write marker protocol uses a simple enhancement to the read/write protocol
of Section 2.2: we introduce a write quorum marker field to all variables. That is,
for a replicated variable Z , each server u maintains, in addition to Z u and T u , a
third value W u , which is the name of the quorum (e.g., an n-bit vector indicating
the servers in the quorum) used to complete the write operation in which Z u and T u
were last written. The write protocol proceeds as in Section 2.2, except that in the
last step, in addition to updating Z u and T u to v and T at each server u in a quorum
, the client also updates W u with (the name of) Q 0 . Specifically, to update Z u ,
T u , and W u at all (correct) servers in Q 0 , the client sends a message containing
to each u 2 Q 0 . Because communication is reliable (see Section 2),
the writer knows that Z u , T u and W u will be updated at all correct servers in Q 0 .
As before, each server u updates Z u , T u , and W u to the received values !v; T;
only if T is greater than the present value of T u .
The read protocol proceeds essentially as before, except that each server returns
the triple !Z in response to a read request. From among all triples
returned from at least t servers, the client chooses the triple with the highest
timestamp.
Below we describe two ways of detecting faults by making use of the set of triples
returned by the servers.
4.2 Statistical fault detection
Our revised statistical technique uses the quorum markers to determine the set
S of servers whose returned values would match the accepted triple in the absence
of faults, and the set S 0 of servers whose returned values actually do match that
triple. Because of the size-based construction of threshold quorum systems and the
random selection of the servers that make up the quorum for a given operation, the
set S can be considered a random sample of the servers, of which jS nS 0 j are known
to be faulty. Taking a random variable y to be the number of faulty servers in the
sample, we can use similar calculations to those in Section 3 to analyze with greater
precision the probability that f exceeds t a .
As shown in Section 3, the probability of finding y faults in a sample of size s
given a universe of size n containing f faults is expressed by the hypergeometric
y
s\Gammay
s
Fault Detection for Byzantine Quorum Systems
9 .999660 19 .999999

Table

4: Probability of detecting f ? 0 in Example 3
For a rejection level ff, the region of rejection for the hypothesis a is therefore
defined by the lowest value lowreject such that:
s
y=lowreject
t a
y
n\Gammat a
s\Gammay
s
Again, the left-hand expression represents the parameterized probability of a false
alarm.
For this method, experiments in which t a = 0 are a degenerate case. The presence
of any faults in the intersection set is visible and invalidates the null hypoth-
esis; the probability of a false positive in such cases is zero, as the formula above
confirms. Likewise, as the number of faults increases, the probability of detecting
faults within one or two reads rapidly approaches certainty.
Example 3: Consider again the system of servers, with a fault tolerance
threshold of quorum size of q = 76, and t a = 0, and suppose that a given
read quorum overlaps the previous write quorum in servers (the most likely
overlap, with a probability of about 0.21). The probability of alarm on a single
read operation for various values of f ! t, is shown in Table 4.
A comparison of this table with Table 2 illustrates the dramatically higher precision
of the write-marker method over the justifying set method. This precision has
additional advantages when t a is set to a value greater than 0.
Example 4: Consider again the system of servers, with a fault tolerance
threshold of quorum size of q = 46, and t a = 5, and suppose that a given
read quorum overlaps the previous write quorum in the most common intersection
size servers. The region of rejection for the null hypothesis calculated
using the formula above, is y - 5. The probability of alarm on a single read
operation for various values of f , t a t, is shown in Table 5.
Alvisi, Malkhi, Pierce, Reiter
9

Table

5: Probability of detecting f ? 5 in Example 4
Again, the increased strength of the write-marker method is evident (see Table 3).
Like the method presented in Section 3, the write-marker technique also has the
advantage of flexibility. If we wish to minimize the risk of premature alarms (i.e.,
alarms that are sent without the alarm threshold being exceeded) we may choose a
smaller ff at the risk of somewhat delayed alarms. In fact, the greater precision of
this method decreases
the risks associated with such a course: even delayed alarms can be expected to
be timely.
4.3 Fault identification
The write marker protocol has an even stronger potential as a tool for fault de-
tection: it allows the client to identify specific servers that are behaving incorrectly.
By keeping a record of this list, the client can thereafter select quorums that do not
contain these servers. This allows the system to behave somewhat more efficiently
than it would otherwise, as well as gathering the information needed to isolate faulty
servers for repair so that the system's integrity is maintained.
The fault identification algorithm accepts as input the triples f!Z
that the client obtained from servers in the read protocol, as well as the triple
that the client chose as the result of the read operation. It then computes
the set S n S 0 where is the set of servers that returned
in the read operation. The servers in S n S 0 are identified as faulty.
Note that the fault identification protocol does not depend in any way on the specific
characteristics of threshold quorum systems, and is easily seen to be applicable
to masking quorum systems in general.
5 Choosing alarm lines for large systems
The analysis of the previous two sections is precise but computationally cumbersome
for very large systems. A useful alternative is to estimate the performance
of possible alarm lines by means of bound analysis. In this section we present an
asymptotic analysis of the techniques of Sections 3 and 4 that shows how to choose
an alarm line value for arbitrarily large systems.
Fault Detection for Byzantine Quorum Systems
Let us denote the read quorum Q, the write quorum Q 0 , the set of faulty servers by
B, and the hypothesized size of B (i.e., the alarm line) by t a . We define a random
variable which is the justifying set size. We can compute
the expectation of X directly. For each server u 62 B define an indicator random
variable I u such that I I otherwise. For such u
we have P (I since Q and Q 0 are chosen independently. By linearity
of expectation,
Intuitively, the distribution on X is centered around its expectation and decreases
exponentially as X moves farther away from that expectation. Thus, we should be
able to show that X grows smaller than its expectation with exponentially decreasing
probability. A tempting approach to analyzing this would be to use Chernoff
bounds, but these do not directly apply because the selection of individual servers
in Q (similarly, Q 0 ) is not independent. In the analysis below, we thus use a more
powerful tool, martingales, to derive the anticipated Chernoff-like bound.
We bound the probability using the method of bounded differences,
by defining a suitable Doob martingale sequence and applying Azuma's inequality
(see [MR95, Ch. 4.4] for a good exposition of this technique; Appendix A provides
a brief introduction). Here, a Doob martingale sequence of conditional random
variables is defined by setting q, to be the expected value of X after i
selections are made in each of Q and Q 0 . Then, and it is
not difficult to see that jX This yields the following
bound (see Appendix A).
We use this formula and our desired rejection level ff to determine a ffi such that
probability value is our probability of a false alarm
and can be diminished by decreasing ff and recalculating ffi. The value
defines our region of rejection (see Section 2.3).
In order to analyze the probability that our alarm is triggered when the number
of faults in the system is t 0 ? t a , we define a second random variable X 0 identical
to X except for the revised failure hypothesis. This gives us:
An analysis similar to the above provides the following bound:
To summarize, these bounds can now be used as follows. For any given alarm line
t a , and any desired confidence level ff, we can compute the minimum ffi to satisfy
Alvisi, Malkhi, Pierce, Reiter
We thus derive the following test: An alarm is triggered whenever the
justifying set size is less than (n \Gamma t a
ffi. The analysis above guarantees that this
alarm will be triggered with false positive probability at most our computed bound
ff. If, in fact, f faults occur and f is sufficiently larger than t a , then there
exists by the analysis above, the
probability of triggering the alarm is greater than
8q .
In the case of the write marker protocol, we can tighten the analysis by using
the (known) intersection size between Q and Q 0 as follows.
Bj. Y has a hypergeometric distribution
on s, )=n. The appropriate Doob martingale
sequence in this case defines Y i , s, to be the expected value of Y after i
selections are made in S. Then, jY and so to set the region of rejection
we can use
6 Conclusion
In this paper, we have presented two methods for probabilistic fault diagnosis
for services replicated using t-masking quorum systems. Our methods mine server
responses to read operations for evidence of server failures, and if necessary trigger
an alarm to initiate appropriate recovery actions. Both of our methods were demonstrated
in the context of the threshold construction of [MR97a], i.e., in which the
quorums are all sets of size d n+2t+1e, but our techniques of Section 4 can be generalized
to other masking quorum systems, as well. Our first method has the advantage
of requiring no modifications to the read and write protocols proposed in [MR97a].
The second method requires minor modifications to these protocols, but also offers
better diagnosis capabilities and a precise identification of faulty servers. Our methods
are very effective in detecting faulty servers, since faulty servers risk detection
in every read operation to which they return incorrect answers.
Future work will focus on generalizations of these techniques, as well as uses
of these techniques in a larger systems context. In particular, we are presently
exploring approaches to react to server failures once they are detected.



--R

Unreliable failure detectors for reliable distributed sys- tems
Muteness detectors for consensus with Byzantine pro- cesses
Solving consensus in a Byzantine environment using an unreliable failure detector.
The SecureRing protocols for securing group communication.
On interprocess communication (part II: algorithms).
On the resilience of multicasting strategies in a failure-propagating environment
Randomized algorithms.
Byzantine quorum systems.
Unreliable intrusion detection in distributed computation.
The load and availability of Byzantine quorum systems.
Secure agreement protocols: Reliable and atomic group multicast in Rampart.
Reliable scheduling in a TMR database system.
Implementing fault-tolerant services using the state machine ap- proach: A tutorial
Principal features of the VOLTAN family of reliable node architectures for distributed systems.
--TR
Randomized algorithms
A <inline-equation> <f> <rad><rcd>N</rcd></rad></f> </inline-equation> algorithm for mutual exclusion in decentralized systems
Unreliable failure detectors for reliable distributed systems
Synchronous Byzantine quorum systems
Probabilistic Byzantine quorum systems
The Load and Availability of Byzantine Quorum Systems
Intrusion Detection
An Architecture for Survivable Coordination in Large Distributed Systems
Fault Detection for Byzantine Quorum Systems
Unreliable Intrusion Detection in Distributed Computations
A comparison connection assignment for diagnosis of multiprocessor systems

--CTR
Andreas Haeberlen , Petr Kouznetsov , Peter Druschel, The case for Byzantine fault detection, Proceedings of the 2nd conference on Hot Topics in System Dependability, p.5-5, November 08, 2006, Seattle, WA
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
byzantine fault tolerance;replicated data;fault detection;quorum systems