On scalable and efficient distributed failure detectors.
Process groups in distributed applications and services rely on failure detectors to detect process failures completely, and as quickly, accurately, and scalably as possible, even in the face of unreliable message deliveries. In this paper, we look at quantifying the optimal scalability, in terms of network load, (in messages per second, with messages having a size limit) of distributed, complete failure detectors as a function of application-specified requirements. These requirements are 1) quick failure detection by some non-faulty process, and 2) accuracy of failure detection. We assume a crash-recovery (non-Byzantine) failure model, and a network model that is probabilistically unreliable (w.r.t. message deliveries and process failures). First, we characterize, under certain independence assumptions, the optimum worst-case network load imposed by any failure detector that achieves an application's requirements. We then discuss why traditional heart beating schemes are inherently unscalable according to the optimal load. We also present a randomized, distributed, failure detector algorithm that imposes an equal expected load per group member. This protocol satisfies the application defined constraints of completeness and accuracy, and speed of detection on an average. It imposes a network load that differs frown the optimal by a sub-optimality factor that is much lower than that for traditional distributed heartbeating schemes. Moreover, this sub-optimality factor does not vary with group size (for large groups).
INTRODUCTION
Failure detectors are a central component in fault-tolerant
distributed systems based on process groups running over
unreliable, asynchronous networks eg., group membership
protocols [3], supercomputers, computer clusters [13], etc.
The ability of the failure detector to detect process failures
completely and e#ciently, in the presence of unreliable messaging
as well as arbitrary process crashes and recoveries,
can have a major impact on the performance of these sys-
tems. "Completeness" is the guarantee that the failure of
a group member is eventually detected by every non-faulty
group member. "E#ciency" means that failures are detected
quickly, as well as accurately (i.e., without too many mis-
takes).
The first work to address these properties of failure detectors
was by Chandra and Toueg [5]. The authors showed
why it is impossible for a failure detector algorithm to deterministically
achieve both completeness and accuracy over
an asynchronous unreliable network. This result has lead to
a flurry of theoretical research on other ways of classifying
failure detectors, but more importantly, has served as
a guide to designers of failure detector algorithms for real
systems. For example, most distributed applications have
opted to circumvent the impossibility result by relying on
failure detector algorithms that guarantee completeness deterministically
while achieving e#ciency only probabilistically
[1, 2, 4, 6, 7, 8, 14].
The recent emergence of applications for large scale distributed
systems has created a need for failure detector algorithms
that minimize the network load (in bytes per second,
or equivalently, messages per second with a limit on maximum
message size) used, as well as the load imposed on
participating processes [7, 14]. Failure detectors for such
settings thus seek to achieve good scalability in addition to
e#ciency, while still (deterministically) guaranteeing completeness

Recently, Chen et al. [6] proposed a comprehensive set of
metrics to measure the Quality of Service (QoS) of complete
and e#cient failure detectors. This paper presented three
primary metrics to quantify the performance of a failure detector
at one process detecting crash-recovery failures of a
single other process over an unreliable network. The authors
proposed failure detection time, and recurrence time and duration
times of mistaken detection as the primary metrics for
complete and e#cient failure detectors. However, the paper
neither deal with the optimal relation among these metrics,
nor focussed on distributed or scalable failure detectors.
In this paper, we first address the question of quantifying
the optimum worst-case network load (in messages per sec-
ond, with a limit on messages sizes) needed by a complete
distributed failure detector protocol to satisfy the e#ciency
requirements as specified by the application. We are concerned
with distributed failure detectors working in a group
of uniquely identifiable processes, which are subject to failures
and recoveries, and communicate over an unreliable net-
work. We deal with complete failure detectors that satisfy
application-defined e#ciency constraints of 1) (quickness)
detection of any group member failure by some non-faulty
member within a time bound, and 2) (accuracy) probability
(within this time bound) of no other non-faulty member
detecting a given non-faulty member as having failed.
The first (quickness) requirement merits further discussion.
Many systems, such as multi-domain server farm clusters [7,
13] and virtual synchrony implementations [3] rely on a single
or a few central computers to aggregate failure detection
information from across the system. These computers are
then responsible for disseminating that information across
the entire system. In such systems, e#cient detection of
a failure depends on the time the failure is first detected
by a non-faulty member. Even in the absence of a central
server, notification of a failure is typically communicated,
by the first member to detect it, to the entire group via a
(possibly unreliable) broadcast [3]. Thus, although achieving
completeness is important, e#cient detection of a failure
is more often related with the time to the first detection, by
another non-faulty member, of the failure.
We derive the optimal worst-case network load (in messages
per second, with a limit on maximum message size) imposed
on the network by a complete failure detector satisfying the
above application-defined constraints. We then discuss why
the traditional and popular distributed heartbeating failure
detection schemes (eg., [7, 14]) do not achieve these optimal
scalability limits. Finally, we present a randomized
distributed failure detector that can be configured to meet
the application-defined constraints of completeness and ac-
curacy, and expected speed of detection. With reasonable
assumptions on the network unreliability (member and message
failure rates of up to 15%), the worst-case network load
imposed by this protocol has a sub-optimality factor that is
much lower than that of traditional distributed heartbeat
schemes. This sub-optimality factor does not depend on
group size (in large groups), but only on the application-
specified e#ciency constraints and the network unreliability
probabilities. Furthermore, the average load imposed per
member is independent of the group size.
In arriving at these results, we will assume that message loss
and member failures can each be characterized by probabilistic
distributions, independent across messages and failures.
While the practicality of these assumptions in real networks
will probably be subject to criticism, these assumptions are
necessary in order to take this first step towards quantifying
and achieving scalable and e#cient failure detectors. Be-
sides, we believe that these independence assumptions are
partially justified because of 1) the randomized nature of the
new failure detector algorithm, and 2) the large temporal
separation between protocol periods, typically O(seconds)
in practice (mitigating much of the correlation among message
loss probability distributions).
The rest of the paper is organized as follows. Section 2
briefly summarizes previous work in this area. In Section 3,
we formally describe the process group model assumed in
this paper. Section 4 presents a discussion of how an application
can specify e#ciency requirements to a failure de-
tector, and quantifies the optimal worst-case network load
a failure detector must impose, in order to meet these re-
quirements. Section 5 presents the new randomized failure
detector protocol. We conclude in section 6.
2. PREVIOUS WORK
Chandra and Toueg [5] were the first to formally address
the completeness and accuracy properties of failure detec-
tors. Subsequent work has focused on di#erent properties
and classifications of failure detectors. This area of literature
has treated failure detectors as oracles used to solve the
Distributed Consensus/Agreement problem [9], which is unsolvable
in the general asynchronous network model. These
classifications of failure detectors are primarily based on the
weakness of the model required to implement them, in order
to solve the Distributed Consensus/Agreement problem
[11].
Proposals for implementable failure detectors have sometimes
assumed network models with weak unreliability semantics
eg., timed-asynchronous model [8], quasi-synchronous
model [2], partial synchrony model [12], etc. These proposals
have treated failure detectors only as a tool to e#ciently
reach agreement, ignoring their e#ciency from an application
designer's viewpoint. For example, most failure detectors
such as [12] provide eventual guarantees, while applications
are typically concerned about real timing constraints.
In most real-life distributed systems, the failure detection
service is implemented via variants of the "Heartbeat mech-
anism" [1, 2, 4, 6, 7, 8, 14], which have been popular as
they guarantee the completeness property. However, all existing
heartbeat approaches have shortcomings. Centralized
heartbeat schemes create hot-spots that prevent them from
scaling. Distributed heartbeat schemes o#er di#erent levels
of accuracy and scalability depending on the exact heart-beat
dissemination mechanism used, but we show that they
are inherently not as e#cient and scalable as claimed.
Probabilistic network models have been used to analyze heart-beat
failure detectors in [4, 6], but only with a single process
detecting failures of a single other process. [6] was the first
paper to propose metrics for non-distributed heartbeat failure
detectors in the crash-recovery model. These metrics
were not inclusive of scalability concerns.
Our work di#ers from all this prior work in that it is the
first to approach the design of failure detectors from a distributed
application developer's viewpoint. We quantify the
performance of a failure detector protocol as the network
load it requires to impose on the network, in order to satisfy
the application-defined constraints of completeness, and
quick and accurate detection 1 . We also present an e#cient
and scalable distributed failure detector. The new failure
detector incurs a constant expected load per process, thus
We will state these application-defined requirements formally
in Section 4.
avoiding the hot-spot problem of centralized heartbeating
schemes.
3. MODEL
We consider a large group of n (# 1) members 2 . This set of
potential group members is fixed a priori. Group members
have unique identifiers. Each group member maintains a
list, called a view, containing the identities of all other group
members (faulty or otherwise). Our protocol specification
and analysis assumes that this maximal group membership
is always the same at all members, but our results can be
extended to a model with dynamically changing membership
and members with incomplete views, using methodologies
similar to [10].
Members may su#er crash (non-Byzantine) failures, and recover
subsequently. Unlike other papers on failure detectors
(eg., [14]) that consider a member as faulty if they are perturbed
and sleep for a time greater than some pre-specified
duration, our notion of failure considers that a member is
faulty if and only if it has really crashed. Perturbations at
members that might lead to message losses are accounted for
in the message loss rate pml (which we will define shortly).
Whenever a member recovers from a failure, it does so into
a new incarnation that is distinguishable from all its earlier
incarnations. At each member, an integer in non-volatile
storage, that is incremented every time the member recov-
ers, su#ces to serve as the member's incarnation number.
The members in our group model thus have crash-recovery
semantics with incarnation numbers distinguishing di#erent
failures and recoveries. When a member M i crashes (fails),
it does so in its current incarnation (say its l'th incarnation).
We say that such a failure is "detected" at exactly the first
instant of time that some other non-faulty member detects
either 1) failure of M i in incarnation greater than or equal
to l, or 2) recovery of M i in an incarnation strictly greater
than l.
We characterize the member failure probability by a parameter
f is the probability that a random group member
is faulty at a random time. Member crashes are assumed to
be independent across members.
We assume no synchronization of clocks across group mem-
bers. We only require that each individual member's clock
drift rate (from some fixed clock rate) remains constant.
Members communicate using unicast (point-to-point) messaging
on an asynchronous, fault-prone network. Since we
are interested in characterizing the network bandwidth uti-
lized, we will assume that maximal message sizes are a con-
stant, containing at most a few bytes of data (assuming a
bound on the size of message identifiers and headers, as is
typical in IP packets).
Each message sent out on the network fails to be delivered
at its recipient (due to network congestion, bu#er overflow
at the sender or receiver due to member perturbations, etc.)
with probability pml # (0, 1). The worst-case message prop-
2 All of which are either processes, or servers, or network
adaptors etc.
agation delay (from sender to receiver through the network)
for any delivered message is assumed to be so small compared
to the application-specified detection time (typically
O( several seconds )) that henceforth, for all practical pur-
poses, we can assume that each message is either delivered
immediately at the recipient with probability (1 - pml ), or
never reaches the recipient. 3
This message loss distribution is also assumed to be independent
across messages. Message delivery losses could, in fact,
be correlated in such a network. However, if application-
specified failure detection times are much larger than message
propagation and congestion repair times in the network,
messages exchanged by the failure detector will have considerable
temporal separation. This reduces the correlation
among the loss distributions of di#erent messages. Randomized
selection of message destinations in the new failure
detector also weakens such message loss correlation.
In the rest of the paper, we use the shorthands q f and qml
instead of (1 - pf ) and (1 - pml ) respectively.
4. SCALABLE AND EFFICIENT FAILURE
The first formal characterization of the properties of failure
detectors was o#ered in [5], which laid down the following
properties for distributed failure detectors in process groups:
. fStrong/Weakg Completeness: crash-failure of any
group member is detected by {all/some} non-faulty
members 4 ,
. Strong Accuracy: no non-faulty group member 5 is
declared as failed by any other non-faulty group member

[5] also showed that a perfect failure detector i.e., one which
satisfies both Strong Completeness and Strong Accuracy, is
su#cient to solve distributed Consensus, but is impossible
to implement in a fault-prone network.
Subsequent work on designing e#cient failure detectors has
attempted to trade o# the Completeness and Accuracy properties
in several ways. However, the completeness properties
required by most distributed applications have lead to
the popular use of failure detectors that guarantee Strong
Completeness always, even if eventually [1, 2, 4, 5, 6, 7,
8, 14]. This of course means that such failure detectors
cannot guarantee Strong Accuracy always, but only with a
probability less than 1. For example, all-to-all (distributed)
3 This assumption is made for simplicity. In fact, the optimality
results of section 4 hold if pml is assumed to be the
probability of message delivery within T time units after its
send. The randomized protocol of section 5 and its analysis
can be extended to hold if pml is the probability of message
delivery within a sixth of the protocol period.
4 Recollect that in our model, since members recover with
unique incarnations, detection of a member's failure or recovery
also implies detection of failure of all it's previous
incarnations.
5 in its current incarnation
heartbeating schemes have been popular because they guarantee
Strong Completeness (since a faulty member will stop
sending heartbeats), while providing varying degrees of accuracy

We have explained in Section 1 why in many distributed
applications, although the failure of a group member must
eventually be known to all non-faulty members, it is important
to have the failure detected quickly by some non-faulty
member (and not necessarily all non-faulty members). In
other words, the quickness of failure detectors depends on
the time from a member failure to Weak Completeness with
respect to that failure, although Strong Completeness is a
necessary property.
The requirements imposed by an application (or its designer)
on a failure detector protocol can thus be formally specified
and parameterized as follows:
1. Completeness: satisfy eventual Strong Completeness
for member failures.
2. Efficiency:
(a) Speed: every member failure is detected by some
non-faulty group member within T time units after
its occurrence (T # worst-case message round
time).
(b) Accuracy: at any time instant, for every non-faulty
member M i not yet detected as failed, the
probability that no other non-faulty group member
will (mistakenly) detect M i as faulty within
the next T time units is at least (1 - PM(T )).
T and PM(T ) are thus parameters specified by the application
(or its designer). For example, an application designer
might specify
To measure the scalability of a failure detector algorithm, we
use the worst-case network load it imposes - this is denoted
as L. Since several messages may be transmitted simultaneously
even from one group member, we define:
Definition 1. The worst-case network load L of a failure
detector protocol is the maximum number of messages transmitted
by any run of the protocol within any time interval
of length T , divided by T .
We also require that the failure detector impose a uniform
expected send and receive load at each member due to this
tra#c.
The goal of a near-optimal failure detector algorithm is thus
to satisfy the above requirements (Completeness, Effi-
ciency) while guaranteeing:
. Scale: the worst-case network load L imposed by the
algorithm is close to the optimal possible, with equal
expected load per member.
That brings us to the question - what is the optimal worst-case
network load, call it L # , that is needed to satisfy the
above application-defined requirements - Completeness,
Speed (T ), Accuracy are able to answer
this question in the network model discussed earlier
when the group size n is very large (# 1), and PM(T ) is
very small ( # pml ).
Theorem 1. Any distributed failure detector algorithm
for a group of size n (# 1) that deterministically satisfies the
Completeness, Speed, Accuracy requirements above, for
given values of T and PM(T ) (# pml ), imposes a minimal
worst-case network load (messages per time unit, as defined
above) of:
log(pml
Furthermore, there is a failure detector that achieves this
minimal worst-case bound while satisfying the Complete-
ness, Speed, Accuracy requirements.
L # is thus the optimal worst-case network load required to
satisfy the Completeness, Speed, Accuracy requirements.
Proof. We prove the first part of the theorem by showing
that each non-faulty group member could transmit up to
log(PM(T
log(p ml )
messages in a time interval of length T .
Consider a group member M i at a random point in time
t. Let M i not be detected as failed yet by any other group
member, and stay non-faulty until at least time
m be the maximum number of messages sent by M i , in the
time interval [t, t any possible run of the failure
detector protocol starting from time t.
Now, at time t, the event that "all messages sent by M i in
the time interval [t, t+T ] are lost" happens with probability
at least p m
ml . Occurrence of this event entails that it is indistinguishable
to the set of the rest of the non-faulty group
members (i.e., members other than M i ) as to whether M i is
faulty or not. By the Speed requirement, this event would
then imply that M i is detected as failed by some non-faulty
group member between t and t
Thus, the probability that at time t, a given non-faulty member
M i that is not yet detected as faulty, is detected as failed
by some other non-faulty group member within the next T
time units, is at least p m
ml . By the Accuracy requirement,
we have p m
ml # PM(T ), which implies that m # log(PM(T
log(p ml ) .
A failure detector that satisfies the Completeness, Speed,
Accuracy requirements and meets the L # bound works as
follows. It uses a highly available, non-faulty server as a
group leader 6 . Every other group member sends [ log(PM(T
log(p ml )
"I am alive" messages to this server every T time units. The
6 The set of central computers, that collect failure information
and disseminate it to the system, can be designated as
the server.
server declares a member as failed when it does not receive
any "I am alive" message from it for T time units 7 .
Corollary: The optimal bound of Theorem 1 applies to the
crash-stop model as well.
Proof: By exactly the same arguments as in the proof of
Theorem 1. 2
Definition 2. The sub-optimality factor of a failure detector
algorithm that imposes a worst-case network load
L, while satisfying the Completeness and Efficiency re-
quirements, is defined as L
In the traditional distributed Heartbeating failure detection
algorithms, every group member periodically transmits a
"heartbeat" message (with an incremented counter) to every
other group member. A member M i is declared as failed
by a non-faulty member M j when M j does not receive heartbeats
from M i for some consecutive heartbeat periods (this
duration being the detection time T ).
Distributed heartbeating schemes have been the most popular
implementation of failure detectors because they guarantee
Completeness - a failed member will not send any
more heartbeat messages. However, the accuracy and scalability
guarantees of heartbeating algorithms di#er, depending
entirely on the actual mechanism used to disseminate
heartbeats.
In the simplest implementation, each member M i transmits
a few "I am alive" messages to each group member it knows
of, every T time units. The worst-case number of messages
transmitted by each member per unit time is #(n), and the
worst-case total network load L is #(n 2 ). The sub-optimality
factor (i.e., L
as #(n), for any values of pml , pf and
The Gossip-style failure detection service, proposed by van
Renesse et al. [14], uses a mechanism where every tgossip
time units, each member gossips a #(n) list of the latest
heartbeat counters (for all group members) to a few other
randomly selected group members. The authors show that
under this scheme, a new heartbeat count typically takes
an average time of #[log(n) - tgossip ] to reach an arbitrary
other group member. The Speed requirement thus leads
us to choose
log(n) ]. The worst-case network
load imposed by the Gossip-style heartbeat scheme is thus
T ]. The sub-optimality factor varies as
#[n - log(n)], for any values of pml , pf and PM(T ).
In fact, distributed heartbeating schemes do not meet the
optimality bound of Theorem 1 because they inherently attempt
to communicate a failure notification to all group
members. As we have seen above, this is an overkill for
systems that can rely on a centralized coordinated set of
7 This implementation, which is essentially a centralized
heartbeat mechanism, is undesirable as it requires a highly
available server and has bad load balancing (does not satisfy
the Scale property).
servers to disseminate failure information. These systems
require only some other non-faulty member to detect a given
failure.
Other heartbeating schemes, such as Centralized heartbeating
(as discussed in the proof of Theorem 1) and heartbeating
along a logical ring of group members [7], can be configured
to meet the optimal load L # , but have problems such
as creating hot-spots (centralized heartbeating) or unpredictable
failure detection times in the presence of multiple
simultaneous faults at larger group sizes (heartbeating in a
ring).
5. A RANDOMIZED DISTRIBUTED
In the preceding sections, we have characterized the optimal
worst-case load imposed by a distributed failure detector
that satisfies the Completeness, Speed and Accuracy
requirements, for application specified values of T and
(Theorem 1). We have then studied why traditional
heartbeating schemes are inherently not scalable.
In this section, we relax the Speed condition to detect a failure
within an expected (rather than exact, as before) time
bound of T time units after the failure. We then present a
randomized distributed failure detector algorithm that guarantees
Completeness with probability 1, detection of any
member failure within an expected time T from the failure,
and an Accuracy probability of (1 -PM(T )). The protocol
imposes an equal expected load per group member, and
a worst-case (and average case) network load L that di#ers
from the optimal L # of Theorem 1 by a sub-optimality factor
(i.e., L
that is independent of group size n (# 1). In such
large groups, at reasonable values of member and message
delivery failure rates pf and pml , this sub-optimality factor
is much lower than the sub-optimality factors of the traditional
distributed heartbeating schemes discussed in the
previous section.
5.1 New Failure Detector Algorithm
The failure detector algorithm uses two parameters: protocol
period T # (in time units) and integer k, which is the size
of failure detection subgroups. We will show how the values
of these parameters can be configured from the required values
of T and PM(T ), and the network parameters p f , pml .
Parameters T # and k are assumed to be known a priori at
all group members. Note that this does not need clocks
to be synchronized across members, but only requires each
member to have a steady clock rate to be able to measure
The algorithm is formally described in Figure 1. At each
non-faulty member M i , steps (1-3) are executed once every
units (which we call a protocol period), while steps
are executed whenever necessary. The data contained
in each message is shown in parentheses after the message. If
sequence numbers are allowed to wrap around, the maximal
message size is bounded from above.

Figure

2 illustrates the protocol steps initiated by a member
during one protocol period of length T # time units. At
the start of this protocol period at M i , a random member
Integer pr; /* Local period number */
Every T # time units at
1. Select random member M j from view
Send a ping(M i , M j , pr) message to M j
Wait for the worst-case message round-trip time for
an
2. If have not received an ack(M i , M j , pr) message yet
Select k members randomly from view
Send each of them a ping-req(M i , M j , pr) message
Wait for an ack(M i , M j , pr) message until
the end of period pr
3. If have not received an ack(M i , M j , pr) message yet
Declare M j as failed
Anytime at
4. On receipt of a ping-req(Mm ,
Send a ping(M i , M j , Mm , pr) message to M j
On receipt of an ack(M i , M j , Mm , pr) message from M j
Send an ack(Mm , M j , pr) message to received to Mm
Anytime at
5. On receipt of a ping(Mm , M i , M l , pr) message from
member Mm
Reply with an ack(Mm , M i , M l , pr) message to Mm
Anytime at
6. On receipt of a ping(Mm , M i , pr) message from member Mm
Reply with an ack(Mm , M i , pr) message to Mm

Figure

1: Protocol steps at a group member M i .
Data in each message is shown in parentheses after
the message. Each message also contains the current
incarnation number of the sender.
is selected, in this case M j , and a ping message sent to it.
If M i does not receive a replying ack from M j within some
time-out (determined by the message round-trip time, which
is # T ), it selects k members at random and sends to each
a ping-req message. Each of the non-faulty members among
these k which receives the ping-req message subsequently
pings M j and forwards the ack received from M j , if any, back
to M i . In the example of Figure 2, one of the k members
manages to complete this cycle of events as M j is up, and
does not suspect M j as faulty at the end of this protocol
period.
In the above protocol, member M i uses a randomly selected
subgroup of k members to out-source ping-req messages,
rather than sending out k repeat ping messages to the target
. The e#ect of using the randomly selected subgroup is
to distribute the decision on failure detection across a sub-group
of members. Although we do not analyze it
in this paper, it can be shown that the new protocol's properties
are preserved even in the presence of some degree of
variation of message delivery loss probabilities across group
members. Sending k repeat ping messages may not satisfy
this property. Our analysis in Section 5.2 shows that the
cost (in terms of sub-optimality factor of network load) of
using a 1)-sized subgroup is not too significant.
5.2 Analysis
In this section, we calculate, for the above protocol, the
expected detection time of a member failure, as well as
the probability of an inaccurate detection of a non-faulty
choose random
choose k random
members
ack
ping
ack
ping
ack
ping

Figure

2: Example protocol period at M i . This
shows all the possible messages that a protocol period
may initiate. Some message contents excluded
for simplicity.
member by some other (at least one) non-faulty member.
This will lead to calculation of the values of T # and k, for
the above protocol, as a function of parameters specifying
application-specified requirements and network unreliabil-
ity, i.e., T , PM(T ), pf , pml .
For any group member M j , faulty or otherwise,
Pr [at least one non-faulty member chooses to
ping M j (directly) in a time interval
Thus, the expected time between a failure of member M j
and its detection by some non-faulty member is
(1)
This gives us a configurable value for T # as a function of
At any given time instant, a non-faulty member M j will be
detected as faulty by another non-faulty member M l within
the next T time units if M l chooses to ping M j within the
next T time units and does not receive any acks, directly
or indirectly from transitive ping-req's, from M j . Then,
PM(T ), the probability of inaccurate failure detection of
member M j within the next T time units, is simply the
probability that there is at least one such member M l in the
group.
A random group member M l is non-faulty with probability
qf , and the probability of such a member choosing to ping
Given this, the
probability that such a M l receives back no acks, direct or
indirect, according to the protocol of section 5.1 equals
Therefore,
This gives us
log[ PM(T )
ml )- e q f
log(1 - qf - q 4
(2)
Thus, the new randomized failure detector protocol can be
configured using equations (1) and (2) to satisfy the Speed
and Accuracy requirements with parameters E[T ], PM(T ).
Moreover, given a member M j that has failed (and stays
failed), every other non-faulty member M i will eventually
choose to ping M j in some protocol period, and discover M j
as having failed. Hence,
Theorem 2. This randomized failure detector protocol:
(a) satisfies eventual Strong Completeness, i.e., the Completeness
requirement,
(b) can be configured via equations (1) and (2) to meet the
requirements of (expected) Speed, and Accuracy, and
(c) has a uniform expected send/receive load at all group
members.
Proof. From the above discussion and equations (1),
(2).
Finally, we upper-bound the worst-case and expected net-work
load (L, E[L] respectively) imposed by this failure detector
protocol.
The worst-case network load occurs when, every T # time
units, each member initiates steps (1-6) in the algorithm
of

Figure

1. Steps (1,6) involve at most 2 messages, while
steps (2-5) involve at most 4 messages per ping-req target
member. Therefore, the worst-case network load imposed
by this protocol (in messages/time unit) is
Then, from Theorem 1 and equations (1),(2),
log[ PM(T )
ml )- e q f
log(1 - qf - q 4
log(PM(T
thus di#ers from the optimal L # by a factor that is independent
of the group size n. Furthermore, (3) can be written
as a linear function of 1
as:
(4a)
where g(pf , pml ) is:
log(1 - q f - q 4
(4b)
and f(pf , pml ) is:
log(1 - qf - q 4
(4c)
Theorem 3. The sub-optimality factor L
L # of the protocol
of

Figure

1, is independent of group size n (# 1). Furthermore

1. if f(pf , pml ) < 0,
(a) L
L # is monotonically increasing with -log(PM(T )),
and
(b) As PM(T
2. if f(p f , pml ) > 0,
(a) L
L # is monotonically decreasing with -log(PM(T )),
and
(b) As PM(T
Proof. From equations (4a) through (4c).
We next calculate the average network load imposed by the
new failure detector algorithm. Every T # time units, each
non-faulty member (numbering (n - q f ) on an average) executes
steps (1-3), in the algorithm of Figure 1. Steps (1,6)
involve at most 2 messages, while steps (2-5) (which are executed
only if no ack is received from the target of the ping
of step (1) - this happens with probability (1 - q f - q 2
ml
involve at most 4 messages per non-faulty ping-req target
member. Therefore, the average network load imposed by
this protocol (in messages/time unit) is
Then, from Theorem 1 and equations (1),(2),
log[ PM(T )
ml )- e q f
log(1 - qf - q 4
log(PM(T
Even E[L] can be upper-bounded from the optimal L # by a
factor that is independent of the group size n.
Do the values of L
very high compared to
the ideal value of 1.0 ? The answer is a 'No' when values
of pf , pml are low, yet reasonable. Figure 3(a) shows
the variation of L
# as in equation (3), at low but reason-able
values of pf , pml , and PM(T ). This plot shows that
the sub-optimality factor of the network load imposed by
the new failure detector rises as pml and pf increase, or
decreases, but is bounded above by the function
g(pf , pml ), at all values of PM(T ). This happens because
at such low values of pf and pml , as seen
from

Figure

3(b) - Theorem 3.1 thus applies here. From
figure 3(a), the function g(pf , pml ) (bottom-most surface),
does not attain too high values (staying below 26 for the
values shown). Thus the performance of the new failure detector
algorithm is good for reasonable assumptions on the
network unreliability.

Figure

3(c) shows that the upper bound on E[L]
very
low (below 8) for values of pf and pml up to 15%. More-
over, as PM(T ) is decreased, the bound on E[L]
actually
decreases. This curve reveals the advantage of using randomization
in the failure detector. Unlike traditional distributed
heartbeating algorithms, the average case network
load behavior of the new protocol is much lower than the
worst-case network load behavior.

Figure

3 reveals that for values of p f and pml below 15%,
the L
L # for the new randomized failure detector stays below
26, and E[L]
8. Further, as is evident from
equations (3) and (5), the variation of these sub-optimality
factors does not depend on the group size (at large group
sizes). Compare this with the sub-optimality factors of distributed
heartbeating schemes discussed in Section 4, which
are typically at least #[n].
In reality, message loss rates and process failure rates could
vary from time to time. The parameters p f and pml , needed
to configure protocol parameters T # and k, may be di#-
cult to estimate. However, Figure 3 shows that assuming
reasonable bounds on these message loss rates/failure rates
and using these bounds to configure the failure detector suf-
fices. In other words, configuring protocol parameters with
ensure that the failure detector preserves
the application specified constraints (T , PM(T imposing
a network load that di#ers from the optimal worst-case
load L # by a factor of at most 26 in the worst-case, and
8 in the average case, as long as the message loss/process
failure rates do not exceed 15% (this load is lower when loss
or failure rates are lower).
(a) Variation of L
(according to equation
versus pml , pf , at di#erent values of
PM(T ). For low values of pml and pf ,
g(pf , pml ) is an upper bound on L
(b) Values of pf , pml for which f(pf , pml ) is
positive or negative.
pf 00.060.12pml26(E[L]/L*) <=
(c) Variation of E[L]
(according to equation (5)).

Figure

3: Performance of new failure detector algorith

5.3 Future Work and Optimizations
At Cornell University, we are currently testing performance
of a scalable distributed membership service that uses the
new randomized failure detection algorithm.
Extending the above protocol to the crash-stop model inherent
to dynamic groups involves several protocol extensions.
Every group member join, leave or failure detection entails a
broadcast to the non-faulty group members in order to up-date
their view. Further, this broadcast may not be reliable.
Implementing this protocol over a group spanning several
subnets requires that the load on the connecting routers or
gateways be low. The protocol currently imposes an O(n)
load (in bytes per second) on such routers during every protocol
period. Reducing this load inevitably leads to compromising
some of the Efficiency properties of the protocol,
as pings are sent less frequently across subnets.
The protocol can also be optimized to trade o# worse Scale
properties for better Accuracy properties. One such optimization
is to follow a failure detection (by an individual
non-faulty member through the described protocol) by
multicast of a suspicion of that failure, waiting for some
time before turning this suspicion into a declaration of a
member failure. With such a suspicion multicast in place,
protocol periods at di#erent non-faulty group members, targeting
this suspected member, can be correlated to improve
the Accuracy properties. This would also reduce the e#ect
of correlated message failures on the frequency of mistaken
failure declarations.
A disadvantage of the protocol is that since messages are restricted
to contain at most a few bytes of data, large message
headers mean higher overheads per message. The protocol
also precludes optimizations involving piggy-backed mes-
sages, primarily due to the random selection of ping targets.
The discussion in this paper also points us to several new
and interesting questions.
Is it possible to design a failure detector algorithm that,
for an asynchronous network setting, satisfies Complete-
ness, Efficiency, Scale requirements, and the Speed requirement
(section with a deterministic bound on time to
detection of a failure (T ), rather than as an average case as
we have done in this paper ? 8 Notice that this is not di#cult
to achieve in a synchronous network setting (by modifying
the new failure detector algorithm to choose ping targets
in a deterministic and globally known manner during every
protocol period).
We also leave as an open problem the specification and realization
of optimality load conditions for a failure detector
with the Speed timing parameter T set as the time to
achieve Strong Completeness for any group member failure
(rather than just Weak Completeness).
8 Heartbeating along a logical ring among group members
(eg., [7]) seems to provide a solution to this question. How-
ever, as pointed out before, ring heartbeating has unpredictable
failure detection times in the presence of multiple
simultaneous failures.
Of course, it would be ideal to extend all such results to
models that assume some degree of correlation among message
losses, and perhaps even member failures.
6. CONCLUDING COMMENTS
In this paper, we have looked at designing complete, scal-
able, distributed failure detectors from timing and accuracy
parameters specified by the distributed application. We
have restricted ourselves to a simple, probabilistically lossy,
network model. Under certain independence assumptions,
we have first quantified the optimal worst-case network load
(messages per second, with a limit on maximal message size)
required by a complete failure detector algorithm in a process
group over such a network, derived from application-
specified constraints of 1) detection time of a group member
failure by some non-faulty group member, and 2) probability
(within the detection time period) of no other non-faulty
member detecting a given non-faulty member as having
failed. We have then shown why the popular distributed
heartbeating failure detection schemes inherently do not satisfy
this optimal scalability limit.
Finally, we have proposed a randomized failure detector algorithm
that imposes an equal expected load on all group
members. This failure detector can be configured to satisfy
the application-specified requirements of completeness
and accuracy, and speed of failure detection (on average).
Our analysis of the protocol shows that it imposes a worst-case
network load that di#ers from the optimal by a sub-optimality
factor greater than 1. For very stringent accuracy
requirements (PM(T ) as low as e -30 ), reasonable message
loss probabilities and process failure rates in the network
(up to 15% each), the sub-optimality factor is not as large as
that of traditional distributed heartbeating protocols. Fur-
ther, this sub-optimality factor does not vary with group
size, when groups are large.
We are currently involved in implementing and testing the
behavior of this protocol in dynamic group membership sce-
narios. This involves several extensions and optimizations
to the described protocol.

Acknowledgments

We thank all the members of the Oc-eano group for their
feedback. We are also immensely grateful to the anonymous
reviewers and Michael Kalantar for their suggestions
towards improving the quality of the paper.
7.



--R

Heartbeat: a timeout-free failure detector for quiescent reliable communication
Timing failure detection and real-time group communication in real-time systems
The process group approach to reliable distributed computing.
Probabilistic analysis of a group failure detection protocol.
Unreliable failure detectors for reliable distributed systems.
On the quality of service of failure detectors.


Impossibility of distributed Consensus with one faulty process.
A probabilistically correct leader election protocol for large groups.
Solving Agreement problems with failure detectors
Optimal implementation of the weakest failure detector for solving Consensus.
In search of Clusters
A gossip-style failure detection service
--TR
The process group approach to reliable distributed computing
Impossibility of distributed consensus with one faulty process
Unreliable failure detectors for reliable distributed systems
Fail-awareness in timed asynchronous systems
In search of clusters (2nd ed.)
Optimal implementation of the weakest failure detector for solving consensus (brief announcement)
Heartbeat
A Probabilistically Correct Leader Election Protocol for Large Groups
On the Quality of Service of Failure Detectors
Probabilistic Analysis of a Group Failure Detection Protocol

--CTR
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
Jin Yang , Jiannong Cao , Weigang Wu , Corentin Travers, The notification based approach to implementing failure detectors in distributed systems, Proceedings of the 1st international conference on Scalable information systems, p.14-es, May 30-June 01, 2006, Hong Kong
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
Greg Bronevetsky , Daniel Marques , Keshav Pingali , Paul Stodghill, Automated application-level checkpointing of MPI programs, ACM SIGPLAN Notices, v.38 n.10, October
Wei Xu , Jiannong Cao , Beihong Jin , Jing Li , Liang Zhang, GCS-MA: A group communication system for mobile agents, Journal of Network and Computer Applications, v.30 n.3, p.1153-1172, August, 2007
On the Implementation of Unreliable Failure Detectors in Partially Synchronous Systems, IEEE Transactions on Computers, v.53 n.7, p.815-828, July 2004
Andrei Korostelev , Johan Lukkien , Jan Nesvadba , Yuechen Qian, QoS management in distributed service oriented systems, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.345-352, February 13-15, 2007, Innsbruck, Austria
Kelvin C. W. So , Emin Gn Sirer, Latency and bandwidth-minimizing failure detectors, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
Michel Reynal, A short introduction to failure detectors for asynchronous distributed systems, ACM SIGACT News, v.36 n.1, March 2005
scalability;failure detectors;efficiency;distributed systems;accuracy