On the Quality of Service of Failure Detectors.
Editor's Note: This paper unfortunately contains some errors which led to the paper being reprinted in the May 2002 issue. Please see IEEE Transactions on Computers, vol. 51, no. 5, May 2002, pp. 561-580 for the correct paper (available without subscription).We study the quality of service (QoS) of failure detectors. By QoS, we mean a specification that quantifies 1) how fast the failure detector detects actual failures and 2) how well it avoids false detections. We first propose a set of QoS metrics to specify failure detectors for systems with probabilistic behaviors, i.e., for systems where message delays and message losses follow some probability distributions. We then give a new failure detector algorithm and analyze its QoS in terms of the proposed metrics. We show that, among a large class of failure detectors, the new algorithm is optimal with respect to some of these QoS metrics. Given a set of failure detector QoS requirements, we show how to compute the parameters of our algorithm so that it satisfies these requirements and we show how this can be done even if the probabilistic behavior of the system is not known. We then present some simulation results that show that the new failure detector algorithm provides a better QoS than an algorithm that is commonly used in practice. Finally, we suggest some ways to make our failure detector adaptiveto changes in the probabilistic behavior of the network.
Introduction
Fault-tolerant distributed systems are designed to provide reliable and continuous service despite the
failures of some of their components. A basic building block of such systems is the failure detector.
Failure detectors are used in a wide variety of settings, such as network communication protocols [10],
computer cluster management [23], group membership protocols [5, 9, 7, 27, 22, 21], etc.
Roughly speaking, a failure detector provides some information on which processes have crashed.
This information, typically given in the form of a list of suspects, is not always up-to-date or correct:
Research partially supported by NSF grant CCR-9711403 and an Olin Fellowship.
y Oracle Corporation, One Oracle Drive, Nashua, NH 03062, USA. Email: Wei.Chen@oracle.com
z DIX Departement d'Informatique, Ecole Polytechnique, 91128 Palaiseau Cedex, France. Email:
sam@dix.polytechnique.fr
x Compaq Systems Research Center, 130 Lytton Avenue, Palo Alto, CA 94301-1044, USA. Email:aguilera@pa.dec.com
a failure detector may take a long time to start suspecting a process that has crashed, and it may erroneously
suspect a process that has not crashed (in practice this can be due to message losses and
delays).
Chandra and Toueg [12] provide the first formal specification of unreliable failure detectors and
show that they can be used to solve some fundamental problems in distributed computing, namely,
consensus and atomic broadcast. This approach was later used and generalized in other works, e.g.,
[20, 16, 17, 1, 3, 2].
In all of the above works, failure detectors are specified in terms of their eventual behavior (e.g.,
a process that crashes is eventually suspected). Such specifications are appropriate for asynchronous
systems, in which there is no timing assumption whatsoever. 1 Many applications, however, have some
timing constraints, and for such applications, failure detectors with eventual guarantees are not suf-
ficient. For example, a failure detector that starts suspecting a process one hour after it crashed can
be used to solve asynchronous consensus, but it is useless to an application that needs to solve many
instances of consensus per minute. Applications that have timing constraints require failure detectors
that provide a quality of service (QoS) with some quantitative timeliness guarantees.
In this paper, we study the QoS of failure detectors in systems where message delays and message
losses follow some probability distributions. We first propose a set of metrics that can be used to specify
the QoS of a failure detector; these QoS metrics quantify (a) how fast it detects actual failures, and (b)
how well it avoids false detections. We then give a new failure detector algorithm and analyze its QoS in
terms of the proposed metrics. We show that, among a large class of failure detectors, the new algorithm
is optimal with respect to some of these QoS metrics. Given a set of failure detector QoS requirements,
we show how to compute the parameters of our algorithm so that it satisfies these requirements, and
we show how this can be done even if the probabilistic behavior of the system is not known. Finally,
we give simulation results showing that the new failure detector algorithm provides a better QoS than
an algorithm that is commonly used in practice. The QoS specification and the analysis of our failure
detector algorithm is based on the theory of stochastic processes. To the best of our knowledge, this
work is the first comprehensive and systematic study of the QoS of failure detectors using probability
theory.
1.1 On the QoS Specification of Failure Detectors
We consider message-passing distributed systems in which processes may fail by crashing, and messages
may be delayed or dropped by communication links. 2 A failure detector can be slow, i.e., it may
take a long time to suspect a process that has crashed, and it can make mistakes, i.e., it may erroneously
suspect some processes that are actually up (such a mistake is not necessarily permanent: the failure
Even though the fail-aware failure detector of [17] is implemented in the "timed asynchronous" model, its specification
is for the asynchronous model.
We assume that process crashes are permanent, or, equivalently, that a process that recovers from a crash assumes a
new identity.
up
trust
suspect
trust
suspect
FD at q

Figure

1: Detection time T D
detector may later stop suspecting this process). To be useful, a failure detector has to be reasonably
fast and accurate.
In this paper, we propose a set of metrics for the QoS specification of failure detectors. In general,
these QoS metrics should be able to describe the failure detector's speed (how fast it detects crashes)
and its accuracy (how well it avoids mistakes). Note that speed is with respect to processes that crash,
while accuracy is with respect to processes that do not crash.
A failure detector's speed is easy to measure: this is simply the time that elapses from the moment
when a process p crashes to the time when the failure detector starts suspecting p permanently. This
QoS metric, called detection time, is illustrated in Fig. 1.
How do we measure a failure detector's accuracy? It turns out that determining a good set of accuracy
metrics is a delicate task. To illustrate some of the subtleties involved, consider a system of two
processes p and q connected by a lossy communication link, and suppose that the failure detector at q
monitors process p. The output of the failure detector at q is either "I suspect that p has crashed" or "I
trust that p is up", and it may alternate between these two outputs from time to time. For the purpose
of measuring the accuracy of the failure detector at q, suppose that p does not crash.
Consider an application that queries q's failure detector at random times. For such an application, a
natural measure of accuracy is the probability that, when queried at a random time, the failure detector
at q indicates correctly that p is up. This QoS metric is the query accuracy probability. For example, in
Fig. 2, the query accuracy probability of FD 1 at q is 12=(12
The query accuracy probability, however, is not sufficient to fully describe the accuracy of a failure
detector. To see this, we show in Fig. 2 two failure detectors FD 1 and FD 2 such that (a) they have the
same query accuracy probability, but (b) FD 2 makes mistakes more frequently than FD 1 . 3 In some
applications, every mistake causes a costly interrupt, and for such applications the mistake rate is an
important accuracy metric.
Note, however, that the mistake rate alone is not sufficient to characterize accuracy: as shown in
Fig. 3, two failure detectors can have the same mistake rate, but different query accuracy probabilities.
3 The failure detector makes a mistake each time its output changes from "trust" to "suspect" while p is actually up.
1 .
up

Figure

2: FD 1 and FD 2 have the same query accuracy probability of :75, but the mistake rate of FD 2
is four times that of FD 1
up

Figure

3: FD 1 and FD 2 have the same mistake rate 1=16, but the query accuracy probabilities of FD 1
and FD 2 are :75 and :50, respectively
Even when used together, the above two accuracy metrics are still not sufficient. In fact, it is easy to
find two failure detectors FD 1 and FD 2 , such that (a) FD 1 is better than FD 2 in both measures (i.e.,
it has a higher query accuracy probability and a lower mistake rate), but (b) FD 2 is better than FD 1 in
another respect: specifically, whenever FD 2 makes a mistake, it corrects this mistake faster than FD
in other words, the mistake durations in FD 2 are smaller than in FD 1 . Having small mistake durations
may be important to some applications.
As it can be seen from the above, there are several different aspects of accuracy that may be important
to different applications, and each aspect has a corresponding accuracy metric.
In this paper, we identify six accuracy metrics (since the behavior of a failure detector is probabilistic,
most of these metrics are random variables). We then use the theory of stochastic processes to quantify
the relation between these metrics. This analysis allows us to select two accuracy metrics as the primary
ones in the sense that: (a) they are not redundant (one cannot be derived from the other), and (b)
together, they can be used to derive the other four accuracy metrics.
In summary, we show that the QoS specification of failure detectors can be given in terms of three
basic metrics, namely, the detection time and the two primary accuracy metrics that we identified.
Taken together, these metrics can be used to characterize and compare the QoS of failure detectors.
1.2 The Design and Analysis of a New Failure Detector Algorithm
In this paper, we consider a simple system of two processes p and q, connected through a communication
link. Process p may fail by crashing, and the link between p and q may delay or drop messages.
Message delays and message losses follow some probabilistic distributions. Process q has a failure detector
that monitors p and outputs either "I suspect that p has crashed" or "I trust that p is up" ("suspect
p" and "trust p" in short, respectively).
A Common Failure Detection Algorithm and its Drawbacks. A simple failure detection algorithm,
commonly used in practice, works as follows: at regular time intervals, process p sends a heartbeat message
to q; when q receives a heartbeat message, it trusts p and starts a timer with a fixed timeout value
if the timer expires before q receives a newer heartbeat message from p, then q starts suspecting p.
This algorithm has two undesirable characteristics; one regards its accuracy and the other its detection
time, as we now explain. Consider the i-th heartbeat message m i . Intuitively, the probability of a
premature timeout on m i should depend solely on m i , and in particular on m i 's delay. With the simple
algorithm, however, the probability of a premature timeout on m i also depends on the heartbeat m
that precedes In fact, the timer for m i is started upon the receipt of m i\Gamma1 , and so if m i\Gamma1 is "fast",
the timer for m i starts early and this increases the probability of a premature timeout on m i . This
dependency on past heartbeats is undesirable.
To see the second problem, suppose p sends a heartbeat just before it crashes, and let d be the delay of
this last heartbeat. In the simple algorithm, q would permanently suspect p only d+TO time units after
crashes. Thus, the worst-case detection time for this algorithm is the maximum message delay plus
TO . This is impractical because in many systems the maximum message delay is orders of magnitude
larger than the average message delay.
The source of the above problems is that even though the heartbeats are sent at regular intervals, the
timers to "catch" them expire at irregular times, namely the receipt times of the heartbeats plus a fixed
TO . The algorithm that we propose eliminates this problem. As a result, the probability of a premature
timeout on heartbeat m i does not depend on the behavior of the heartbeats that precede m i , and the
detection time does not depend on the maximum message delay.
A New Algorithm and its QoS Analysis. In the new algorithm, process p sends heartbeat messages
periodically every j time units (just as in the simple algorithm). To determine whether
to suspect p, q uses a sequence - called freshness points, obtained by
shifting the sending time of the heartbeat messages by a fixed parameter ffi. More precisely, -
where oe i is the time when m i is sent. For any time t, let i be so that t 2 [- trusts p at time
t if and only if q has received heartbeat m i or higher.
Given the probabilistic behavior of the system (i.e., the probability of message losses and the distribution
of message delays), and the parameters j and ffi of the algorithm, we determine the QoS of the
new algorithm using the theory of stochastic processes. Simulation results given in Section 7 are consistent
with our QoS analysis, and they show that the new algorithm performs better than the common
one.
In contrast to the common algorithm, the new algorithm guarantees an upper bound on the detection
time. Moreover, the new algorithm is optimal in the sense that it has the best possible query accuracy
probability with respect to any given bound on the detection time. More precisely, we show that among
all failure detectors that send heartbeats at the same rate (they use the same network bandwidth) and
satisfy the same upper bound on the detection time, the new algorithm has the best query accuracy
probability.
The first version of our algorithm (described above) assumes that p and q have synchronized clocks.
This assumption is not unrealistic, even in large networks. For example, GPS and Cesium clocks are
becoming accessible, and they can provide clocks that are very closely synchronized (see, e.g., [29]).
When synchronized clocks are not available, we propose a modification to this algorithm that performs
equally well in practice, as shown by our simulations. The basic idea is to use past heartbeat messages to
obtain accurate estimates of the expected arrival times of future heartbeats, and then use these estimates
to find the freshness points. This is explained in Section 6.
Configuring our Algorithm to Meet the Failure Detector Requirements of an Application. Given
a set of failure detector QoS requirements (provided by an application), we show how to compute the
parameters of our algorithm to achieve these requirements. We first do so assuming that one knows the
probabilistic behavior of the system (i.e., the probability distributions of message delays and message
losses). We then drop this assumption, and show how to configure the failure detector to meet the QoS
requirements of an application even when the probabilistic behavior of the system is not known.
1.3 Related Work
In [19], Gouda and McGuire measure the performance of some failure detector protocols under the
assumption that the protocol stops as soon as some process is suspected to have crashed (even if this
suspicion is a mistake). This class of failure detectors is less general than the one that we studied here:
in our work, a failure detector can alternate between suspicion and trust many times.
In [28], van Renesse et. al. propose a scalable gossip-style randomized failure detector protocol.
They measure the accuracy of this protocol in terms of the probability of premature timeouts. 4 The
probability of premature timeouts, however, is not an appropriate metric for the specification of failure
detectors in general: it is implementation-specific and it cannot be used to compare failure detectors
that use timeouts in different ways. This point is further explained at the end of Section 2.3.
In [24], Raynal and Tronel present an algorithm that detects member failures in a group: if some
process detects a failure in the group (perhaps a false detection), then all processes report a group failure
and the protocol terminates. The algorithm uses heartbeat-style protocol, and its timeout mechanism is
the same as the simple algorithm that we described in Section 1.2.
4 This is called "the probability of mistakes" in [28].
In [29], Ver-ssimo and Raynal study QoS failure detectors - these are detectors that indicate when
a service does not meet its quality-of-service requirements. In contrast, this paper studies the QoS of
failure detectors, i.e., how well a failure detector works.
Heartbeat-style failure detectors are commonly used in practice. To keep both good detection time
and good accuracy, many implementations rely on special features of the operating system and communication
system to try to ensure that heartbeat messages are received at regular intervals (see discussion
in Section 12.9 of [23]). This is not easy even for closely-connected computer clusters, and it is very
hard in wide-area networks.
The probabilistic network model used in this paper is similar to the ones used in [14, 6] for probabilistic
clock synchronization. The method of estimating the expected arrival times of heartbeat messages
is close to the method of remote clock reading of [6].
The rest of the paper is organized as follows. In Section 2, we propose a set of metrics to specify
the QoS of failure detectors. In Section 3, we describe a new failure detector algorithm and analyze
its QoS in terms of these metrics; we also present an optimality result. We then explain how to set
the algorithm's parameters to meet some given QoS requirements - first in the case when we know
the probabilistic behavior of messages (Section 4), and then in the case when this is not known (Sec-
tion 5). In Section 6 we deal with unsynchronized clocks. We present the results of some simulations
in Section 7, and we conclude the paper with some discussion in Section 8. Appendix A lists the main
symbols used in the paper, and Appendices B to D give the proofs of the main theorems. More detailed
proofs can be found in [13].
2 On the QoS Specification of Failure Detectors
We consider a system of two processes p and q. We assume that the failure detector at q monitors p,
and that q does not crash. Henceforth, real time is continuous and ranges from 0 to 1.
2.1 The Failure Detector Model
The output of the failure detector at q at time t is either S or T , which means that q suspects or trusts
p at time t, respectively. A transition occurs when the output of the failure detector at q changes: An
S-transition occurs when the output at q changes from T to S; a T-transition occurs when the output at
q changes from S to T . We assume that there are only a finite number of transitions during any finite
time interval.
Since the behavior of the system is probabilistic, the precise definition of our model and of our QoS
metrics uses the theory of stochastic processes. To keep our presentation at an intuitive level, we omit
the technical details related to this theory (they can be found in [13]).
We consider only failure detectors whose behavior eventually reaches steady state, as we now explain
informally. When a failure detector starts running, and for a while after, its behavior depends on the
trust
suspect suspect
up
FD at q

Figure

4: Mistake duration T M , good period duration T G , and mistake recurrence time T MR
initial condition (such as whether initially q suspects p or not) and on how long it has been running.
Typically, as time passes the effect of the initial condition gradually diminishes and its behavior no
longer depends on how long it has been running - i.e., eventually the failure detector behavior reaches
equilibrium, or steady state. In steady state, the probability law governing the behavior of the failure
detector does not change over time. The QoS metrics that we propose refer to the behavior of a failure
detector after it reaches steady state. Most of these metrics are random variables.
2.2 Primary Metrics
We propose three primary metrics for the QoS specification of failure detectors. The first one measures
the speed of a failure detector. It is defined with respect to the runs in which p crashes.
Detection time (T D Informally, T D is the time that elapses from p's crash to the time when q starts
suspecting p permanently. More precisely, T D is a random variable representing the time that elapses
from the time that p crashes to the time when the final S-transition (of the failure detector at q) occurs
and there are no transitions afterwards (Fig. 1). If there is no such final S-transition, then T
such an S-transition occurs before p crashes, then T
We next define some metrics that are used to specify the accuracy of a failure-detector. Throughout
the paper, all accuracy metrics are defined with respect to failure-free runs, i.e., runs in which p does
not crash. 6 There are two primary accuracy metrics:
Mistake recurrence time (T MR
this measures the time between two consecutive mistakes. More
precisely, T MR is a random variable representing the time that elapses from an S-transition to the next
one (Fig. 4).
Mistake duration (T M this measures the time it takes the failure detector to correct a mistake. More
precisely, T M is a random variable representing the time that elapses from an S-transition to the next
T-transition (Fig. 4).
As we discussed in the introduction, there are many aspects of failure detector accuracy that may be
important to applications. Thus, in addition to T MR
and T M , we propose four other accuracy metrics
in the next section. We selected T MR and T M as the primary metrics because given these two, one can
5 We omit the boundary cases of other metrics since they can be similarly defined.
6 As explained in [13], these metrics are also meaningful for runs in which p crashes.
compute the other four (this will be shown in Section 2.4).
2.3 Derived Metrics
We propose four additional accuracy metrics:
Average mistake rate (- M this measures the rate at which a failure detector make mistakes, i.e., it is
the average number of S-transitions per time unit. This metric is important to long-lived applications
where each failure detector mistake (each S-transition) results in a costly interrupt. This is the case for
applications such as group membership and cluster management.
Query accuracy probability (P A this is the probability that the failure detector's output is correct at a
random time. This metric is important to applications that interact with the failure detector by querying
it at random times.
Many applications can make progress only during good periods - periods in which the failure
detector makes no mistakes. This observation leads to the following two metrics.
Good period duration (T G this measures the length of a good period. More precisely, T G is a random
variable representing the time that elapses from a T-transition to the next S-transition (Fig. 4).
For short-lived applications, however, a closely related metric may be more relevant. Suppose that
an application is started at a random time in a good period. If the remaining part of the good period is
long enough, the short-lived application will be able to complete its task. The metric that measures the
remaining part of the good period is:
Forward good period duration (T FG this is a random variable representing the time that elapses
from a random time at which q trusts p, to the time of the next S-transition.
At first sight, it may seem that, on the average, T FG
is just half of T G (the length of a good period).
But this is incorrect, and in Section 2.4 we give the actual relation between T FG and T G .
An important remark is now in order. For timeout-based failure detectors, the probability of premature
timeouts has sometimes been used as the accuracy measure: this is the probability that when the
timer is set, it will prematurely timeout on a process that is actually up. The measure, however, is not
appropriate because: (a) it is implementation-specific, and (b) it is not useful to applications unless it is
given together with other implementation-specific measures, e.g., how often timers are started, whether
the timers are started at regular or variable intervals, whether the timeout periods are fixed or variable,
etc. (many such variations exist in practice [10, 19, 28]). Thus, the probability of premature timeouts is
not a good metric for the specification of failure detectors, e.g., it cannot be used to compare the QoS
of failure detectors that use timeouts in different ways. The six accuracy metrics that we identified in
this paper do not refer to implementation-specific features, in particular, they do not refer to timeouts
at all.
2.4 How the Accuracy Metrics are Related
Theorem 1 below explains how our six accuracy metrics are related. We then use this theorem to justify
our choice of the primary accuracy metrics. Henceforth, Pr(A) denotes the probability of event A;
E(X), E(X k ), and V(X) denote the expected value (or mean), the k-th moment, and the variance of
random variable X , respectively.
Parts (2) and (3) of Theorem 1 assume that in failure-free runs, the probabilistic distribution of failure
detector histories is ergodic. Roughly speaking, this means that in failure-free runs, the failure detector
slowly "forgets" its past history: from any given time on, its future behavior may depend only on its
recent behavior. We call failure detectors satisfying this ergodicity condition ergodic failure detectors.
Ergodicity is a basic concept in the theory of stochastic processes [26], but the technical details are
substantial and outside the scope of this paper.
We have also determined the relations between our accuracy metrics in the case that ergodicity does
not hold. The resulting expressions are more complex (they are generalized versions of those given
below) and can be found in [13].
Theorem 1 For any ergodic failure detector, the following results hold: (1) T . (2) If
is always 0. If
R x
In particular,
(3c) E(T FG
The fact that T holds is immediate by definition. The proofs of parts (2) and (3) use the
theory of stochastic processes. Part (2) is intuitive, while part (3), which relates T G and T FG
, is more
complex. In particular, part (3c) is counter-intuitive: one may think that E(T FG
(3c) says that E(T FG ) is in general larger than E(T G )=2 (this is a version of the "waiting time paradox"
in the theory of stochastic processes [4]).
We now explain how Theorem 1 guided our selection of the primary accuracy metrics. Parts (2) and
(3) show that - M , P A and T FG
can be derived from T MR
This suggests that the primary
metrics should be selected among T MR , T M and T G . Moreover, since T it is clear that
given the joint distribution of any two of them, one can derive the remaining one. Thus, two of T MR
T M and T G should be selected as the primary metrics, but which two? By choosing T MR
and T M as
our primary metrics, we get the following convenient property that helps to compare failure detectors:
if FD 1 is better than FD 2 in terms of both E(T MR ) and E(T M ) (the expected values of the primary
metrics) then we can be sure that FD 1 is also better than FD 2 in terms of E(T G ) (the expected values
of the other metric). We would not get this useful property if T G were selected as one of the primary
metrics. 7
7 For example, FD 1 may be better than FD 2 in terms of both E(T G ) and E(T M ), but worse than FD 2 in terms of
E(T MR ).
3 The Design and QoS Analysis of a New Failure Detector Algorith

3.1 The Probabilistic Network Model
We assume that processes p and q are connected by a link that does not create or duplicate messages, 8
but may delay or drop messages. Note that the link here represents an end-to-end connection and does
not necessarily correspond to a physical link.
We assume that the message loss and message delay behavior of any message sent through the link
is probabilistic, and is characterized by the following two parameters: (a) message loss probability
which is the probability that a message is dropped by the link; and (b) message delay D, which is a
random variable with range (0; 1) representing the delay from the time a message is sent to the time
it is received, under the condition that the message is not dropped by the link. We assume that the
expected value E(D) and the variance V(D) of D are finite. Note that our model does not assume that
the message delay time D follows any particular distribution, and thus it is applicable to many practical
systems.
have access to their own local clocks. For simplicity, we assume that there is no
clock drift, i.e., local clocks run at the same speed as real time (our results can be easily generalized to
the case where local clocks have bounded drifts). In Sections 3, 4 and 5, we further assume that clocks
are synchronized. We explain how to remove this assumption in Section 6.
For simplicity we assume that the probabilistic behavior of the network does not change over time.
In Section 8, we explain how to modify the algorithm so that it dynamically adapts to changes in the
probabilistic behavior of the system.
We assume that crashes cannot be predicted, i.e., the state of the system at any given time has no
information whatsoever on the occurrence of future crashes (this excludes a system with program-controlled
crashes [11]). Moreover, the delay and loss behaviors of the messages that a process sends
are independent of whether (and when) the process crashes.
3.2 The Algorithm
The new algorithm works as follows. The monitored process p periodically sends heartbeat messages
to q every j time units, where j is a parameter of the algorithm. Every heartbeat
message m i is tagged with its sequence number i. Henceforth, oe i denotes the sending time of message
. The monitoring process q shifts the oe i 's forward by ffi - the other parameter of the algorithm -
to obtain the sequence of times uses the - i 's and the
times it receives heartbeat messages, to determine whether to trust or suspect p, as follows. Consider
8 Message duplication can be easily taken care of: whenever we refer to a message being received, we change it to the
first copy of the message being received. With this modification, all definitions and analyses in the paper go through, and in
particular, our results remain correct without any change.
(c)
(b)
(a)
FD at q
suspect
trust trust
suspect

Figure

5: Three scenarios of the failure detector output in one interval [-
Process p:
1 for all i - 1, at time oe
Process q:
3 for all i - 1, at time -
4 if did not receive m j with j - i then output fsuspect p if no fresh message is receivedg
5 upon receive message m j at time t 2 [-
ftrust p when some fresh message is receivedg

Figure

Failure detector algorithm NFD-S with parameters j and ffi (clocks are synchronized)
time period [- checks whether it has received some message m j with j - i. If so,
trusts p during the entire period [- starts suspecting p. If at some time
before - i+1 , q receives some message m j with j - i then q starts trusting p from that time until - i+1 .
(Fig. 5 (b)). If by time - i+1 , q has not received any message m j with j - i, then q suspects p during
the entire period [- This procedure is repeated for every time period. The detailed
algorithm with parameters j and ffi is denoted by NFD-S, and is given in Fig. 6. 9
Note that from time - i to - i+1 , only messages m j with j - i can affect the output of the failure
detector. For this reason, - i is called a freshness point: from time - i to - i+1
are still fresh (useful). With this algorithm, q trusts p at time t if and only if q received a message that
is still fresh at time t.
9 This version of the algorithm is convenient for illustrating the main idea and for performing the analysis. We have
omitted some obvious optimizations.
3.3 The QoS Analysis of the Algorithm
We now give the QoS of the algorithm (the analysis is given in Appendix B). We assume that the link
from p to q satisfies the following message independence property: the behaviors of any two heartbeat
messages sent by p are independent. 10 Henceforth, let - 0
(as in line 3 of
the algorithm).
We first formalize the intuition behind freshness points and fresh messages:
Lemma 2 For all trusts p at time t if and only if q has received some
message t.
The following definitions are for runs where p does not crashes.
(1) For any i - 1, let k be the smallest integer such that for all is sent at or after time
(2) For any i - 1, let p j (x) be the probability that q does not receive message m i+j by time
for every j - 0 and every x - 0; let
(3) For any i - 2, let q 0 be the probability that q receives message m
(4) For any i - 1, let u(x) be the probability that q suspects p at time
(5) For any i - 2, let p S be the probability that an S-transition occurs at time - i .
The above definitions are given in terms of i, a positive integer. Proposition 3, however, shows that
they are actually independent of i.
Proposition 3 (1) dffi=je. (2) For all
By definition, if the probability that q receives m i by time - i is 1. Thus,
Similarly, it is easy to see that if
are degenerated cases of
no interest. We henceforth assume that
The following theorem summarizes our QoS analysis of the new failure detector algorithm.
In practice, this holds only if consecutive heartbeats are sent more than some \Delta time units apart, where \Delta depends on
the system. So assuming that the behavior of heartbeats are independent is equivalent to assuming that j ? \Delta.
Theorem 4 Consider a system with synchronized clocks, where the probability of message losses is
and the distribution of message delays is P (D - x). The failure detector NFD-S of Fig. 6 with
parameters j and ffi has the following properties.
(1) The detection time is bounded:
(2) The average mistake recurrence time is:
E(T MR
(3) The average mistake duration is:
From E(T MR ) and E(T M ) given in the theorem above, we can easily derive the other accuracy measures
using Theorem 1. For example, we can get the query accuracy probability P
Theorem 4 (1) shows an important property of the algorithm: the detection time is bounded, and the
bound does not depend on the behavior of message delays and losses.
In Sections 4, 5 and 6, we show how to use Theorem 4 to compute the failure detector parameters,
so that the failure detector satisfies some QoS requirements (given by an application).
3.4 An Optimality Result
Among all failure detectors that send heartbeats at the same rate and satisfy the same upper bound on
the detection time, the new algorithm provides the best query accuracy probability. More precisely, let
C be the class of failure detector algorithms A such that in every run of A, process p sends heartbeats
to q every j time units and A satisfies T D - T U
for some constant T U
. Let A   be the instance of the
new failure detector algorithm NFD-S with parameters j and
j. By part (1) of Theorem 4,
we know that A   2 C. We can show that
Theorem 5 For any A 2 C, let P A be the query accuracy probability of A. Let P
A
be the query
accuracy probability of A   . Then P
A
The theorem is a consequence of the following important property of algorithm A   . Consider any
algorithm A 2 C. Let r be any failure-free run of A   , and r 0 be any failure-free run of A in which the
heartbeat delays and losses are exactly as in r. We can show that if q suspects p at time t in r, then q
also suspects p at time t in r 0 . With this property, it is easy to see that the probability that q trusts p at
a random time in A   must be at least as high as the probability that q trusts p at a random time in any
A 2 C. The detailed proof is given in Appendix C.
Failure Detector
Configurator
QoS
Requirements
U
MR
U
Pr (D - x)
Probabilistic Behavior
of Heartbeats

Figure

7: Meeting QoS requirements with NFD-S. The probabilistic behavior of heartbeats is given,
and clocks are synchronized
4 Configuring the Failure Detector to Satisfy QoS Requirements
Suppose we are given a set of failure detector QoS requirements (the QoS requirements could be given
by the application that uses this failure detector). We now show how to compute the parameters j and ffi
of our failure detector algorithm, so that these requirements are satisfied. We assume that (a) the local
clocks of processes are synchronized, and (b) one knows the probabilistic behavior of the messages,
i.e., the message loss probability p L and the distribution of message delays Pr(D - x). In Sections 5
and 6, we consider the cases when these assumptions do not hold.
We assume that the QoS requirements are expressed using the primary metrics. More precisely, a set
of QoS requirements is a tuple (T U
MR
of positive numbers, where T U
is an upper bound on the
detection time, T L
MR
is a lower bound on the average mistake recurrence time, and T U
is an upper bound
on the average mistake duration. In other words, the requirements are that: 11
MR
Our goal, illustrated in Fig. 7, is to find a configuration procedure that takes as inputs (a) the QoS re-
quirements, namely T U
MR
, and (b) the probabilistic behavior of the heartbeat messages, namely
p L and Pr(D - x), and outputs the failure detector parameters j and ffi so that the failure detector
satisfies the QoS requirements in (4.4). Furthermore, to minimize the network bandwidth taken by the
failure detector, we want a configuration procedure that finds the largest intersending interval j that
satisfy these QoS requirements.
Using Theorem 4, our goal can be stated as a mathematical programming problem:
11 Note that the bounds on the primary metrics E(T MR ) and E(T M ) also impose bounds on the derived metrics, according
to Theorem 1. More precisely, we have - M - 1=T L
MR
MR
MR
MR
M , and E(T FG
MR
)=2.
subject to
MR
where the values of u(x) and p S are given by Proposition 3. Solving this problem is hard, so instead
we show how to find some j and ffi that satisfy (4.5)-(4.7) (but the j that we find may not be the largest
possible). To do so, we replace (4.7) with a simpler and stronger constraint, and then compute the
optimal solution of this modified problem (see Appendix D). We obtain the following procedure to find
j and ffi:
. If j
"QoS cannot be achieved" and stop; else continue.
ffl Step 2: Let
Find the largest j - j max such that
MR
. Such an j always exists. To find such an j, we
can use a simple numerical method, such as binary search (this works because when j decreases,
increases exponentially fast).
ffl Step 3: Set
Theorem 6 Consider a system in which clocks are synchronized, and the probabilistic behavior of
messages is known. Suppose we are given a set of QoS requirements as in (4.4). The above procedure
has two possible outcomes: (1) It outputs j and ffi. In this case, with parameters j and ffi the failure
detector NFD-S of Fig. 6 satisfies the given QoS requirements. (2) It outputs "QoS cannot be achieved".
In this case, no failure detector can achieve the given QoS requirements.
As an example of the configuration procedure of the failure detector, suppose we have the following
QoS requirements: (a) a crash failure is detected within
s; (b) on average,
the failure detector makes at most one mistake per month, i.e., T L
s; (c) on
average, the failure detector corrects its mistakes within one minute, i.e. T U
Assume that
the message loss probability is p 0:01, the distribution of message delay D is exponential, and the
average message delay E(D) is 0:02 s. By inputting these numbers into the configuration procedure,
we get these parameters, our failure detector satisfies the given QoS
requirements.
Failure Detector
Configurator
Estimator of the Probabilistic
Behavior of Heartbeats
E(D)
QoS
Requirements
U
MR
U

Figure

8: Meeting QoS requirements with NFD-S. The probabilistic behavior of heartbeats is not
known, and clocks are synchronized
5 Dealing with Unknown Message Behavior
In Section 4, our procedure to compute the parameters j and ffi of NFD-S to meet some QoS requirements
assumed that one knows the probability p L of message loss and the distribution Pr(D - x) of
message delays. This assumption is not unrealistic, but in some systems the probabilistic behavior of
messages may not be known. In that case, it is still possible to compute j and ffi, as we now explain.
We proceed in two steps: (1) we first show how to compute j and ffi using only p L , E(D) and V(D)
(recall that E(D) and V (D) are the expected value and variance of message delays, respectively); (2)
we then show how to estimate p L , E(D) and V(D). In this section we still assume that local clocks are
synchronized (we drop this assumption in the next section). See Fig. 8.
Computing Failure Detector Parameters j and ffi Using p L , E(D) and V(D). With E(D) and
V(D), we can bound Pr(D ? t) using the following One-Sided Inequality of probability theory (e.g.,
see [4], p.79): For any random variable D with a finite expected value and a finite variance,
With this, we can derive the following bounds on the QoS metrics of algorithm NFD-S.
Theorem 7 Consider a system with synchronized clocks and assume ffi ? E(D). For algorithm NFD-S,
we have E(T MR
Y
and
Note that in Theorem 7 we assume that ffi ? E(D), where ffi is a parameter of NFD-S. This assumption
is reasonable because if ffi - E(D) then NFD-S would generate a false suspicion every time the
heartbeat message is delayed by more than the average message delay. But then, NFD-S would make
too many mistakes to be a useful failure detector.
Theorem 7 can be used to compute the parameters j and ffi of the failure detector NFD-S, so that it
satisfies the QoS requirements given in (4.4). Recall that these QoS requirements are given as a tuple
MR
is an upper bound on the worst-case detection time, T L
MR
is a lower bound on
the average mistake recurrence time, and T U
is an upper bound on the average mistake duration. The
configuration procedure is given below. This procedure assumes that T U
E(D), i.e., the required
detection time is greater than the average message delay (a reasonable assumption).
cannot be achieved" and stop; else
continue.
ffl Step 2: Let
Y
Find the largest j - j max such that
MR
. Such an j always exists.
ffl Step 3: Set
Notice that the above procedure does not use the distribution Pr(D - x) of message delays; it only
uses p L , E(D) and V(D).
Theorem 8 Consider a system in which clocks are synchronized, and the probabilistic behavior of
messages is not known. Suppose we are given a set of QoS requirements as in (4.4), and suppose
E(D). The above procedure has two possible outcomes: (1) It outputs j and ffi. In this case,
with parameters j and ffi the failure detector NFD-S of Fig. 6 satisfies the given QoS requirements.
(2) It outputs "QoS cannot be achieved". In this case, no failure detector can achieve the given QoS
requirements.
The above configuration procedure works when the distribution of the message delay D is not known
(only E(D) and V (D) are known). To illustrate this procedure, we take the same example as in Section
4, except that we do not assume that the distribution of D is exponential. Specifically, suppose
that the failure detector QoS requirements are that: (a) a crash failure is detected within
onds, i.e., T U
s; (b) on average, the failure detector makes at most one mistake per month,
i.e., T L
MR
s; (c) on average, the failure detector corrects its mistakes within one
minute, i.e. T U
Assume that the message loss probability is p 0:01, the average message
delay E(D) is 0:02 s, and the variance V (D) is also 0:02. By inputting these numbers into the configuration
procedure, we get these parameters, failure detector NFD-S
satisfies the given QoS requirements. Note that when we go from the case that the distribution of D is
known (example of Section 4) to the case that D is not known, j decreases from 9:97 s to 9:71 s. This
corresponds to a slight increase in the heartbeat sending rate (in order to achieve the same given QoS).
Estimating p L , E(D) and V(D). It is easy to estimate p L , E(D) and V(D) using heartbeat messages.
For example, to estimate p L , one can use the sequence numbers of the heartbeat messages to count the
number of "missing" heartbeats, and then divide this count by the highest sequence number received so
far. To estimate E(D) and V(D), we use the synchronized clocks as follows: When p sends a heartbeat
with the sending time S, and when q receives m, q records the receipt time A. In
this way, A \Gamma S is the delay of m. We then compute the average and variance of A \Gamma S for multiple
past heartbeat messages, and thus obtain accurate estimates for E(D) and V(D).
6 Dealing with Unknown Message Behavior and Unsynchronized
Clocks
So far, we assumed that the clocks of p and q are synchronized. More precisely, in the algorithm NFD-S
of Fig. 6, q sets the freshness points - i 's by shifting the sending times of heartbeats by a constant. When
clocks are not synchronized, the local sending times of heartbeats at p cannot be used by q to set the - i 's,
and thus q needs to do it in a different way. The basic idea is that q sets the - i 's by shifting the expected
arrival times of the heartbeats, and q estimates the expected arrival times accurately (to compute these
estimates, q does not need synchronized clocks).
6.1 NFD-U: an Algorithm that Uses Expected Arrival Times
We now present NFD-U, a new failure detector algorithm for systems with unsynchronized clocks.
The new algorithm is very similar to NFD-S; the only difference is that q now sets the - i 's by shifting
the expected arrival times of the heartbeats, rather than the sending times of heartbeats. We assume
that local clocks do not drift with respect to real time, i.e., they accurately measure time intervals (our
algorithm and results can be easily generalized to the case where local clocks have small bounded drifts
with respect to real time). Let oe i denote the sending time of m i with respect to q's local clock. Then,
the expected arrival time of m i at q is EA E(D) is the expected message delay.
Assume that q knows the EA i 's (we will soon show how q can accurately estimate them). To set the
shifts the EA i 's forward by ff time units (i.e., - ff is a new failure detector
parameter that replaces ffi. The intuition here is that EA i is the time when m i is expected to be received,
and ff is a slack added to EA i to accommodate the possible extra delay or loss of m i .

Figure

9 shows the whole algorithm, denoted by NFD-U. We restructured the algorithm a little, to
Process p: fusing p's local clockg
1 for all i - 1, at time i \Delta j, send heartbeat m i to q;
Process q: fusing q's local clockg
keeps the largest sequence number in all messages q received so farg
the current time: fif the current time reaches - '+1 , then none of the messages received is still freshg
6 output / fsuspect p since no message received is still fresh at this timeg
7 upon receive message m j at time t:
freceived a message with a higher sequence numberg
fset the next freshness point - '+1 using the expected arrival time of m '+1 g
ftrust p since m ' is still fresh at time tg

Figure

9: Failure detector algorithm NFD-U with parameters j and ff (clocks are not synchronized, but
the EA i 's are known)
show explicitly when q uses the EA i 's. Variable ' keeps the largest heartbeat sequence number received
so far, and - '+1 refers to the "next" freshness point. Note that when q updates ', it also changes - '+1 . If
the local clock of q ever reaches time - '+1 (an event which might never happen), then at this time none
of the heartbeats received is still fresh, and so q starts suspecting p (lines 5-6). When q receives m j ,
it checks whether this is a new heartbeat (j ? ') and in this case, (1) q updates ', (2) q sets the next
freshness point - '+1 to EA '+1 + ff, and (3) q trusts p if the current time is less than - '+1 (lines 9-11).
Note that this algorithm is identical to NFD-S, except in the way in which q sets the - i 's. In particular,
for any time t, let i be so that t 2 [- trusts p at time t if and only if q has
received heartbeat m i or higher.
6.2 Analysis and Configuration of NFD-U
NFD-U and NFD-S differ only in the way they set the - i 's: in NFD-S, - while in NFD-U,
last equality holds because EA E(D)). Thus, the QoS
analysis of NFD-U is obtained by simply replacing ffi with E(D) + ff in Proposition 3, Theorem 4 and
Theorem 7.
To configure the parameters j and ff of NFD-U to meet some QoS requirements, we use a method
similar to the one in Section 5. We proceed in two steps: (1) we first show how to compute j and ff
using only p L and V(D) (note that E(D) is not used); (2) we then show how to estimate p L and V(D).
Fig. 10.
Computing Failure Detector Parameters j and ff using p L and V(D). By replacing ffi with E(D)+
ff in Theorem 7, we obtain the following bounds on the accuracy metrics of NFD-U:
Failure Detector NFD-U
are known)
Configurator
Estimator of the Probabilistic
Behavior of Heartbeats
h a
QoS
Requirements
MR
U

Figure

10: Meeting QoS requirements with NFD-U. The probabilistic behavior of heartbeats is not
known; clocks are not synchronized, but they are drift-free
Theorem 9 Consider a system with drift-free clocks and assume ff ? 0. For algorithm NFD-U, we
have E(T MR
Y
Note that the bounds given in Theorem 9 uses only p L and V(D); on the other hand, E(D) is not used.
Theorem 9 can be used to compute the parameters j and ff of the failure detector NFD-U, so that it
satisfies some QoS requirements. We assume the QoS requirements are given as a tuple (T u
MR
of positive numbers. The requirements are that:
MR
Note that the upper bound on the detection time T D is not T u
plus the unknown average
message delay E(D). So, the actual upper bound T U
on the detection time is T u
E(D). In other
words, the QoS requirement on detection time is not absolute as in (4.4), but relative to E(D). This
is justified as follows. Note that when local clocks are not synchronized and only one-way messages
are used, an absolute bound T U
on detection time cannot be enforced by any nontrivial failure detector.
Moreover, it is reasonable to specify an upper bound requirement relative to the average delay E(D)
of a heartbeat. In fact, a failure detector that guarantees to detect crashes faster than E(D) makes too
many mistakes to be useful.
The following is the configuration procedure for algorithm NFD-U, modified from the one in Section
5.
cannot be achieved" and stop; else continue.
ffl Step 2: Let
dT u
Y
Find the largest j - j max such that
MR
. Such an j always exists.
ffl Step 3: Set
Theorem 10 Consider a system with unsynchronized, drift-free clocks, where the probabilistic behavior
of messages is not known. Suppose we are given a set of QoS requirements as in (6.11). The above
procedure has two possible outcomes: (1) It outputs j and ff. In this case, with parameters j and ff the
failure detector NFD-U of Fig. 9 satisfies the given QoS requirements. (2) It outputs "QoS cannot be
achieved". In this case, no failure detector can achieve the given QoS requirements.
Estimating p L and V(D). When local clocks are not synchronized, we can estimate p L and V(D)
using the procedure of Section 5. To estimate p L , this procedure did not use clocks, and so it works
just as before. For V(D), the procedure did use clocks, but it works even though the clocks are not
synchronized. To see why, recall that the procedure estimates V(D) by computing the variance of
of multiple heartbeat messages, where A is the time (with respect to q's local clock time) when
q receives a message m, and S is the time (with respect to p's local clock time) when p sends m. When
clocks are not synchronized, A \Gamma S is not the actual delay of m, but rather the delay of m plus a
constant, namely, the skew between the clocks of p and q. Thus the variance of A \Gamma S is the same as
the variance V(D) of message delays.
6.3 NFD-E: an Algorithm that Uses Estimates of Expected Arrival Times
Failure detector NFD-U (Fig. assumes that q knows the exact value of all the EA i 's (the expected
arrival time of messages). In practice, q may not know such values, and needs to estimate them. To do
so, every time q executes line 10 of algorithm NFD-U in Fig. 9, q considers the n most recent heartbeat
messages (for some n), denoted m 0
be the sequence numbers of such messages
and A 0
n be their receipt times according to q's local clock. Then EA '+1 can be estimated by:
Intuitively, this formula first "normalizes" each A 0
i by shifting it backward in time by js i . Then it
computes the average of the normalized A 0
Finally, it shifts forward the computed average by ('+1)j.
It is easy to see that this is a good estimate of EA '+1 . We denote by NFD-E the algorithm obtained
from Fig. 9 by replacing EA '+1 with this estimate. Our simulations show that NFD-E and NFD-U are
practically indistinguishable for values of n as low as 30. Thus, for large values of n, the configuration
procedure for NFD-U can also be used to configure NFD-E. See Fig. 11.
Failure Detector
Configurator
Estimator of the Probabilistic
Behavior of Heartbeats
h a
QoS
Requirements
MR
U

Figure

Meeting QoS requirements with NFD-E (same as with NFD-U, except that the expected
arrival times EA i 's of heartbeats are estimated)
7 Simulation Results
We simulate both the new failure detector algorithm that we developed and the simple algorithm commonly
used in practice (as described in Section 1.2). In particular, (a) we simulate the algorithm NFD-S
(the one with synchronized clocks), and show that the simulation results validate our QoS analysis of
NFD-S in Section 3.3; (b) we simulate the algorithm NFD-E (the one without synchronized clocks that
estimates the expected arrival times), and show that it provides essentially the same QoS as NFD-S;
and (c) we simulate the simple algorithm and compare it to the new algorithms NFD-S and NFD-E,
and show that the new algorithms provide a much better accuracy than the simple algorithm.
The settings of the simulations are as follows. For the purpose of comparison, we normalize the
intersending time j of heartbeat messages in both the new algorithm and the simple algorithm to 1. The
message loss probability p L is set to 0:01. The message delay D follows the exponential distribution
(i.e., Pr(D - We choose the exponential distribution because of
the following two reasons: first, it has the characteristic that a large portion of messages have fairly
short delays while a small portion of messages have large delays, which is also the characteristic of
message delays in many practical systems [14]; second, it has a simple analytical representation which
allows us to compare the simulation results with the analytical results given in Theorem 4. The average
message delay E(D) is set to 0:02, which is a small value compared to the intersending time j. This
corresponds to a system in which message delays are in the order of tens of milliseconds (typical for
messages transmitted over the Internet), while heartbeat messages are sent every few seconds. Note
that since D follows an exponential distribution, the standard deviation is
the variance is
To compare the accuracy of different algorithms, we first set their parameters so that: (a) they send
messages at the same rate (recall that they satisfy the same bound T U
on the detection
2.5 3 3.5
required bound T U
D on the worst-case detection time
average
mistake
recurrence
time
obtained
from
the
simulations
analytical

Figure

12: The average mistake recurrence times obtained by: (a) simulating the new algorithms NFD-S and
NFD-E (shown by + and \Theta), (b) simulating the simple algorithm (shown by -ffi- and -\Pi-), and (c) plotting the
analytical formula for E(T MR ) of the new algorithm NFD-S (shown by -).
time. We simulated runs for values of T U
ranging from 1 to 3.5, and for each value of T U
, we measured
the accuracy of the failure detectors in terms of the average mistake recurrence time E(T MR ) and the
average mistake duration E(T M ). For each value of T U
, we plotted E(T MR ) by considering a run
with 500 mistake recurrence intervals, and computing the average length of these intervals. We do not
show the plots for E(T M ) because the E(T M ) of all the algorithms were similar and bounded above by
approximately
7.1 Simulation Results of NFD-S and NFD-E
To ensure that NFD-S meets the given upper bound T U
on the detection time, we set ffi to T U
prescribed by Theorem 4 (1)). In algorithm NFD-E, we choose to estimate the expected
arrival time using the most recent messages. To ensure NFD-E meets the given upper
bound T U
, we set
In Fig. 12, we show the simulation results for algorithms NFD-S and NFD-E, together with the
analytical formula of E(T MR ) derived in Section 3.3. These results show that: (a) the accuracy of
algorithms NFD-S and NFD-E are very similar, and (b) the simulation results of both algorithms match
the analytical formula for E(T MR ).
7.2 Simulation Results of the Simple Algorithm
The simple algorithm has no upper bounds on the detection time. However, such an upper bound can
be guaranteed with a simple modification: the general idea is to discard heartbeats which have very
large delays. More precisely, the modified algorithm has another parameter, the cutoff time c, such
that all heartbeats delayed by more than c time units, called slow heartbeats, are discarded. 12 With this
modification, the detection time T D is at most T D - c + TO .
Given a bound T U
on the detection time, there is a tradeoff in setting the cutoff time c and the timeout
the larger the cutoff time c, the smaller the number of slow heartbeats being discarded, but
the shorter the timeout value TO , and vice versa. In our simulations, we choose two cutoff times
times the average message delay, respectively. The timeout TO is
set to T U
c. The algorithm with c = 0:16 is denoted by SFD-L, and the one with
by SFD-S.
The simulation results on the average mistake recurrence times of SFD-L and SFD-S (Fig. 12) show
that the accuracy of the new algorithms (with or without synchronized clocks) is better - sometimes
by an order of magnitude - than the accuracy of the simple algorithm. Intuitively, this is because the
use of a cutoff time to bound the detection time in the simple algorithm is detrimental to its accuracy: if
the simple algorithm uses a large cutoff time, then it must use a small timeout value, and this decreases
the accuracy of the failure detector; if it uses a small cutoff time, then it discards more heartbeats, and
this is equivalent to an increase in the message loss probability; this in turn also decreases the accuracy
of the failure detector (a detailed explanation of the simulation results can be found in [13]).
Concluding Remarks
An Adaptive Failure Detector. In this paper, we assumed that the probabilistic behavior of heartbeat
messages does not change. In some networks, this may not be the case. For instance, a corporate net-work
may have one behavior during working hours (when the message traffic is high), and a completely
different behavior during lunch time or at night (when the system is mostly idle): During peak hours,
the heartbeat messages may have a higher loss rate, a higher expected delay, and a higher variance of
delay, than during off-peak hours. Such networks require a failure detector that adapts to the changing
conditions, i.e., it dynamically reconfigures itself to meet some given QoS requirements.
It turns out that our failure detectors can be made adaptive, as we now explain. For the case when
clocks are synchronized, we make NFD-S adaptive by periodically reexecuting the configuration outlined
in Fig. 8. The basic idea is to periodically run the estimator, which uses the n most recent
heartbeats to estimate the current values of p L ; E(D) and V (D). These estimates are then fed into the
configurator to recompute the new failure detector parameters j and ffi.
This assumes that the algorithm can detect slow messages; this is not easy when local clocks are not synchronized, but
a fail-aware datagram service [18] may be used.
Similarly, when clocks are not synchronized, we can make NFD-E adaptive by periodically reexecuting
the configuration outlined in Fig. 11. The only difference here is that the estimator also outputs EA i
- the estimated arrival time of the next heartbeat - which is input into the failure detector NFD-E.
The above adaptive algorithms form the core of a failure detection service that is currently being implemented
and evaluated [15]. This service is intended to be shared among many different concurrent
applications, each with a different set of QoS requirements. The failure detector in this architecture dynamically
adapts itself not only to changes in the network condition, but also to changes in the current
set of QoS demands (as new applications are started and old ones terminate).

Acknowledgments

We would like to thank Carole Delporte-Gallet, Hugues Fauconnier and anonymous referees of the
conference version of this paper for their useful comments which helped us improve the paper.



--R

Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks.
Failure detection and consensus in the crash-recovery model
On quiescent reliable communication.

Transis: a communication sub-system for high availability
Probabilistic clock synchronization in distributed systems.
Relacs: a communications infrastructure for constructing reliable applications in large-scale distributed systems
Probability and Measure.
Renesse, editors. Reliable Distributed Computing with the Isis Toolkit.
Requirements for Internet Hosts-Communication Layers
On the impossibility of group membership.
Unreliable failure detectors for reliable distributed systems.
On the Quality of Service of Failure Detectors.
Probabilistic clock synchronization.
Failure detector service for dependable computing (fast abstract).
Failure detectors in omission failure environ- ments


Accelerated heartbeat protocols.
Non blocking atomic commitment with an unreliable failure detector.
The Ensemble System.
A fault-tolerant multicast group communication system
In Search of Clusters.
Group membership failure detection: a simple protocol and its probabilistic analysis.
Stochastic Processes.
--TR
Probability, statistics, and queueing theory with computer science applications
Unreliable failure detectors for reliable distributed systems
Totem
Horus
On the impossibility of group membership
In search of clusters (2nd ed.)
Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks
On Quiescent Reliable Communication
Reliable Distributed Computing with the ISIS Toolkit
Probabilistic Clock Synchronization in Distributed Systems
Time in Distributed System Models and Algorithms
Non blocking atomic commitment with an unreliable failure detector
Fail-aware failure detectors
A Fail-Aware Membership Service
Accelerated Heartbeat Protocols
Failure Detectors in Omission Failure Environments
The ensemble system
On the quality of service of failure detectors

--CTR
Xuanhua Shi , Hai Jin , Weizhong Qiang, ALTER: first step towards dependable grids, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Tiejun Ma , Jane Hillston , Stuart Anderson, Evaluation of the QoS of crash-recovery failure detection, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, On implementing omega with weak reliability and synchrony assumptions, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.306-314, July 13-16, 2003, Boston, Massachusetts
Y. Horita , K. Taura , T. Chikayama, A Scalable and Efficient Self-Organizing Failure Detector for Grid Applications, Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, p.202-210, November 13-14, 2005
probabilistic analysis;failure detectors;quality of service;fault tolerance;distributed algorithm