Theoretical Analysis for Communication-Induced Checkpointing Protocols with Rollback-Dependency Trackability.
AbstractRollback-Dependency Trackability (RDT) is a property that states that all rollback dependencies between local checkpoints are on-line trackable by using a transitive dependency vector. In this paper, we address three fundamental issues in the design of communication-induced checkpointing protocols that ensure RDT. First, we prove that the following intuition commonly assumed in the literature is in fact false: If a protocol forces a checkpoint only at a stronger condition, then it must take, at most, as many forced checkpoints as a protocol based on a weaker condition. This result implies that the common approach of sharpening the checkpoint-inducing condition by piggybacking more control information on each message may not always yield a more efficient protocol. Next, we prove that there is no optimal on-line RDT protocol that takes fewer forced checkpoints than any other RDT protocol for all possible communication patterns. Finally, since comparing checkpoint-inducing conditions is not sufficient for comparing protocol performance, we present some formal techniques for comparing the performance of several existing RDT protocols.
Introduction
A distributed computation consists of a finite set of processes connected by a communication
network, that communicate and synchronize by exchanging messages through the network.
A local checkpoint is a snapshot of the local state of a process, saved on nonvolatile storage
to survive process failures. It can be reloaded into volatile memory in case of a failure
to reduce the amount of lost work. When a process has to record such a local state, we
say that this process takes a (local) checkpoint. With each distributed computation is
thus associated a checkpoint and communication pattern, defined from the set of messages
and local checkpoints. A global checkpoint [1] is a set of local checkpoints, one from each
process, and a global checkpoint M is consistent if no message is sent after a checkpoint
of M and received before another checkpoint of M [2]. The computation of consistent
global checkpoints is an important work when one is interested in designing or implementing
systems that have to ensure dependability of the applications they run.
Many protocols have been proposed to select local checkpoints in order to form consistent
global checkpoints (see the survey [3]). Remark that if local checkpoints are taken independently
there is a risk that no consistent global checkpoint can ever be formed from them (this
is the well-known unbounded domino effect , that can occur during rollback-recovery [4]). To
avoid the domino effect, a kind of coordination in the determination of local checkpoints is
required. In [2, 5], the coordination is achieved at the price of synchronization by means of
additional control messages. Another approach, namely, communication-induced checkpointing
[6], achieves coordination by piggybacking control information on application messages.
In that case, processes select local checkpoints independently (called basic checkpoints) and
the protocol requires them to take additional local checkpoints (called forced checkpoints)
in order to ensure the progression of a consistent recovery line. Forced checkpoints are taken
according to certain condition tested each time a message is received, on the basis of control
information piggybacked on messages.
Generally, the fact that two local checkpoints be not causally related is a necessary
but not sufficient condition for them to belong to the same consistent global checkpoint
[7]. They can have "hidden" dependencies that make them impossible to belong to the
same consistent global checkpoint. These dependencies are characterized by the fact that
they cannot be tracked with transitive dependency vectors. To solve this problem, Wang
has defined the Rollback-Dependency Trackability (RDT) property [8]. A checkpoint and
communication pattern satisfies this property if all dependencies between local checkpoints
can be on-line trackable (i.e. trackable by a simple use of the transitive dependency vector).
RDT has two noteworthy properties: (1) It ensures that any set of local checkpoints that are
not pairwise causally related can be extended to form a consistent global checkpoint; (2) It
enjoys efficient calculations of the minimum and the maximum consistent global checkpoints
that contain a given set of local checkpoints. As a consequence, the RDT property has
applications in a large family of dependability problems such as: software error recovery [9],
deadlock recovery [10], mobile computing [11], distributed debugging [12], etc. Moreover,
when combined with an appropriate message logging protocol [13], RDT allows to solve some
dependability problems posed by nondeterministic computations as if these computations
were piecewise deterministic [8].
Since the RDT property has a wide range of applications on many problems, it becomes
an important pragmatic issue to design an efficient communication-induced checkpointing
protocols satisfying the RDT property. The number of forced checkpoints and the size
of piggybacked control information are dominant factors on the price to be paid. Hence
the main question in this context is: how to design an efficient RDT protocol with less
number of forced checkpoints and smaller size of piggybacked control information? Is the
common intuition in the literature [8, 14], "If a protocol forces a checkpoint at a weaker
condition then it must force at least as many checkpoints as a protocol that does at a
stronger condition.", necessarily true (note that the stronger condition is a subset of the
weaker condition)? Is there actually a tradeoff between the number of forced checkpoints
and the size of piggybacked control information [15]? In this paper, we give a theoretical
analysis for these problems. First, some counterexamples against the previous two statements
are enumerated. We then demonstrate that there is no optimal on-line protocol in terms of
the number of forced checkpoints. Since the common intuition is proved to be invalid, some
interesting techniques of comparing useful protocols are also proposed. These techniques
can be used to compare many existing RDT protocols in the literature. Remark that our
results are not only from a theoretical point of view, but also from a practical one, when
considering the task of designing efficient protocols with the RDT property.
This paper is structured in five main sections. Section 2 defines the computational model
and introduces definitions and elements of the Rollback-Dependency Trackability theory. In
Section 3, we discuss some "impossibility " problems. Then several techniques of comparing
useful protocols are addressed in the next section. Section 5 depicts a hierarchy graph for
comparing a family of RDT protocols to marshal the discussions in the context. Finally, we
conclude the paper in Section 6.
2. Preliminaries
2.1 Checkpoint and Communication Patterns
A distributed computation consists of a finite set P of n processes fP that
communicate and synchronize only by exchanging messages. We assume that each ordered
pair of processes is connected by an asynchronous, reliable, directed logical channel whose
transmission delays are unpredictable but finite. Each process runs on a processor; processors
do not share a common memory; there is no bound for their relative speeds and they fail
according to the fail-stop model.
A process can execute internal, send and receive statements. An internal statement does
not involve communication. When P i executes the statement "send(m) to puts the
message m into the channel from P i to P j . When P i executes the statement "receive(m)", it
is blocked until at least one message directed to P i has arrived; then a message is withdrawn
from one of its input channels and received by P i . Executions of internal, send and receive
statements are modeled by internal, sending and receiving events.
Processes of a distributed computation are sequential , in other words, each process P i
produces a sequence of events. This sequence can be finite or infinite. All the events produced
by a distributed computation can be modeled as a partially ordered set with the well-known
!", defined as follows [16].
Definition 1: The relation " hb
!" on the set of events satisfies the following three condition:
(1) If a and b are events in the same process and a comes before b, then a hb
b. (2) If a is
the event send(m) and b is the event receive(m), then a hb
b. (3) If a hb
a hb
With each distributed computation is associated a checkpoint and communication pat-
tern, which is composed of a distributed computation H and the set of local checkpoints
!!!!!!!!!!!!! I k,1 I k,2

Figure

1: A checkpoint and communication pattern ccpat.
defined on H. Figure 1 shows an example checkpoint and communication pattern ccpat.
C i;x represents the xth checkpoint of process and the sequence of events occurring at P i
between C called a checkpoint interval and is denoted by I i;x ; where
i is called the process id and x the index of this checkpoint or this checkpoint interval. We
assume each process P i starts its execution with an initial checkpoint C i;0 .
2.2 Rollback-Dependency Trackability
First we will briefly introduce the concepts of Z-path [7] and causal doubling of a Z-path [15],
and then the concept of Rollback-Dependency Trackability [8]. For more details on these
subjects, please consult those papers previously cited.
Definition 2: A Z-path is a sequence of messages [m
each t.
To the best of our knowledge this notion has been introduced for the first time by Netzer
and Xu in [7] under the name zig-zag path. If a Z-path [m is such that
we say that this Z-path is from I i;x to I j;y . For
example, in pattern ccpat depicted in Figure 1, both the paths [m are
Z-path from I k;2 to I i;2 . However the path [m is not a Z-path. In the rest of this
paper, we use the following notation. In a Z-path -, the first (last) message will be denoted
-:first (-:last). Let - and - be two Z-paths whose concatenation is also a Z-path. This
concatenation will be represented as - \Delta -.
We now introduce the notion of a causal Z-path. A Z-path is causal if the receiving event
of each message except the last one precedes the sending event of the next message in the
sequence. A Z-path is non-causal if it is not causal. A Z-path with only one message is
trivially causal. For simplicity, a casual Z-path will also be called a causal path.
Definition 3: A Z-path from I i;x to I j;y is causally doubled if or if there exists
a causal path - from I i;x 0 to I j;y 0 where x - x 0 and y 0 - y.
From the previous definition, every causal path is obviously causally doubled by itself.
As an example, the Z-path [m in pattern ccpat of Figure 1 is non-causal, and is causally
doubled by the causal path [m
The following concept, Rollback-Dependency Trackability , was introduced by Wang in [8].
It is defined differently but equivalently as below [15].
Definition 4: A checkpoint and communication pattern ccpat satisfies the RDT property
if and only if all non-causal Z-paths are causally doubled in ccpat.
In other words, a checkpoint and communication pattern satisfies this property in the
sense that all dependencies between local checkpoints need to be on-line trackable since
dependencies can be passed over only along causal paths.
2.3 PCM-paths
For a given checkpoint and communication pattern ccpat, it is not necessary to check that
every non-causal Z-path is causally doubled to ensure that ccpat satisfies the RDT property.
Namely, we can only consider some certain embedded subsets of non-causal Z-paths [15]. An
important subset, PCM-paths, is now introduced.
Definition 5: A causal path - from I i;x to I j;y is prime if every causal path - from I i;x 0
to
I j;y 0 with x - x 0 and y 0 - y satisfies that receive(-:last) hb
receive(-:last).
Intuitively, a prime path from I i;x to I j;y is the first one including the existence of interval
I i;x (i.e. the new dependency on which P j 's current state transitively depends with
the causal past of P j 's current state. A PCM-path - \Delta m is a Z-path that is the concatenation
of a causal path - and a single message m, where - is prime and send(m) hb
receive(-:last).
In pattern ccpat shown in Figure 1, the path [m 5 ] is prime but [m 3 ] is not prime. And the
path [m is a PCM-path. The following theorem is a direct consequence of [15].
Theorem 1: A checkpoint and communication pattern ccpat satisfies the RDT property if
and only if all PCM-paths are causally doubled in ccpat.
The idea behind this theorem is that according to the definitions of RDT, since all
dependencies between local checkpoints must be on-line trackable, any new dependency has
to be passed over along a Z-path to its end. Due to all new dependencies included by prime
causal paths firstly, that all PCM-paths are causally doubled is then necessary and sufficient
to ensure the RDT property.
Note that we can exploit the following transitive dependency tracking mechanism proposed
in the literature [11, 17, 18] to detect the existence of a prime path: In a system with
processes, each process P i maintains the size-n transitive dependency vector (TDV), that
can represent the current interval index (or equivalently the checkpoint index of the next
checkpoint) of P i and record the highest index of intervals of any other process P j on which
current state transitively depends. TDV is piggybacked on application messages sent,
and upon the receipt of messages, processes can decide by evaluating this vector if a prime
path is encountered [8].
According to Theorem 1, in order to ensure the RDT property, any PCM-path which
is not causally doubled needs to be broken by a forced checkpoint. For a PCM-path - \Delta m
whose breakpoint is I i;x , on the receipt of -:last, process P i has to distinguish if - \Delta m is
causally doubled, only through the information carried on the message. So this PCM-path
has to be not only causally doubled but also visibly doubled , defined as follows [15], in
order not to be broken.
Definition visibly doubled if and only if it is causally doubled by
a causal path - 0 with receive(- 0 :last) hb
send(-:last).

Figure

2 shows an example visibility of doubling. Intuitively a causal doubling of a PCM-
path is visible at a process on the receipt of message -:last, if the path - 0 that causally
doubles belongs to the causal past of -:last. Note that from the definition a causally
doubled PCM-path is not necessarily visibly doubled, but a non-causally doubled one must
be non-visibly doubled. Based on the foregoing discussion and Theorem 1, we can deduce
a characterization of the RDT with respect to protocols based on the entire-causal history
[15].
Corollary 1: A checkpoint and communication pattern produced by a protocol based on
the entire-causal history satisfies the RDT property if and only if all PCM-paths are visibly
doubled.
-.last

Figure

2: Visibility of doubling.
If a PCM-path is from an interval I i;x to another interval I i;x 0 of the same process P i , we
call this PCM-path a PCM-cycle. If x PCM-cycle can not be causally doubled,
and is called a non-doubled PCM-cycle [15]. For example, the path [m Figure 1 is
a PCM-cycle and is non-doubled. In the remainder of the paper, for the sake of clarity, we
only refer to a PCM-path from a process to another different one as a PCM-path, and on
the contrary, the PCM-path from a process to the same one as a PCM-cycle. PCM-paths
and PCM-cycles are all called PCM-conditions.
3. Impossibility Problems
In this section, we discuss some "impossibility " problems. First we disprove the truthfulness
of the following common intuition in the literature [8, 14]: if a protocol forces a checkpoint at
a weaker condition then it must force at least as many checkpoints as a protocol that does at a
stronger condition. In other words, even though conditions involved in two different protocols
have inclusive and subordinative relationship, it may be impossible to compare these two
protocols in terms of the number of forced checkpoints. The motive of this problem is that
since any forced checkpoint will change the given checkpoint and communication pattern
and consequently affect the later condition testings, as soon as two protocols differ in their
decision to force a checkpoint, the two resulting checkpoint and communication patterns
are not the same and possibly strongly "diverge" in the future, and thus it is perhaps
impossible to compare these two protocols. We also overthrow the concept that there is
a tradeoff between the number of forced checkpoints and the size of piggybacked control
information for RDT protocols. In the last subsection, it was given a proof to demonstrate
another impossibility problem that there is no optimal on-line protocol that ensures the
RDT property. This scenario is quite common in the area of on-line algorithms due to no
knowledge of future information.
3.1 Common Intuitions Not Necessarily True
Two counterexamples are enumerated against those specious statements mentioned previ-
ously. Their results show the fact that it definitely needs a formal proof for comparison
of two different protocols. Therefore we will propose some techniques of comparing useful
protocols in the next section.
Counterexample 1: CPn is a protocol that breaks all PCM-paths and every PCM-cycle
! send(-:first), and CPm is a protocol that breaks all PCM-paths
and every CM-cycle - \Delta m (a CM-condition is the concatenation of a causal path - which is
not necessarily prime and a single message m where send(m) hb
receive(m) hb
! send(-:first). It can be easily verified that both CPn and CPm break all
non-causally doubled PCM-paths and non-doubled PCM-cycles. Hence these two protocols
are RDT protocols by Theorem 1. And they only need to piggyback TDV on application
messages (note that we apply the consequence of [15] to evaluate the size of piggybacked
control information in this paper and please refer to that paper for more details). Obviously,
CPm forces a checkpoint at a weaker condition than CPn's. As the result shown in Figure
3 (a), CPn must take two forced checkpoints (the diamond box) to make the considered
checkpoint and communication pattern satisfy the RDT property. However, CPm needs
only one forced checkpoint to make the same pattern ensure RDT, depicted in Figure 3
(b). This counterexample shows that CPm forces fewer checkpoints than CPn in the given
checkpoint and communication pattern, and thus disproves the common intuition.
Besides overthrowing the common intuition, the following counterexample also demonstrates
that there is not necessarily a tradeoff between the number of forced checkpoints and
the size of piggybacked control information.
Counterexample 2: Let No-Non-Visibly-Doubled-PCM (NNVD-PCM) a protocol
that breaks all non-visibly doubled PCM-paths and non-doubled PCM-cycles, and No-
PCM-Path a protocol that breaks all PCM-path and non-doubled PCM-cycles. Similarly,
since both protocols break all non-visibly doubled PCM-paths and non-doubled PCM-cycles,
initial checkpoint forced checkpoint
basic checkpoint
(a)

Figure

3: The scenario of Counterexample 1 (a) CPn (b) CPm.
according to Corollary 1, they are also RDT protocols. Moreover, since NNVD-PCM has
to decide whether a PCM-path is visibly doubled, it needs more piggybacked control information
than No-PCM-Path's. NNVD-PCM takes one more forced checkpoint (see

Figure

4 (a)) than No-PCM-Path does (see Figure 4 (b)). Hence this counterexample also
shows that the protocol piggybacking less control information (No-PCM-Path) outperforms
the one piggybacking more control information (NNVD-PCM) in some checkpoint
and communication patterns in terms of the number of forced checkpoints.
The idea behind those counterexamples is that the forced checkpoint taken by the protocol
based on the stronger condition will make the CM-path at the rightmost part of the considered
checkpoint and communication pattern become a non-causally doubled PCM-path, and
thus another checkpoint is necessary to be forced to break this PCM-path. However, the
forced checkpoint taken by the protocol on the weaker condition will not give rise to such a
scenario.
initial checkpoint forced checkpoint
basic checkpoint
(a)

Figure

4: The scenario of Counterexample 2 (a) NNVD-PCM (b) No-PCM-Path.
3.2 No Optimal On-line Protocol
We take two categories of on-line protocols into consideration for this problem. These two
categories are on-line protocols based on the entire causal history and the transitive dependency
tracking (i.e. only piggybacking TDV on a message as control information), respec-
tively. They are all shown to have no optimal protocol through the following descriptions.
Given the checkpoint and communication pattern in Counterexample 1, redrawn in Figure
5 and denoted ccpat a , we directly have the following lemma since the PCM-cycle [m
is non-doubled.
Lemma 1: Process P 3 needs to force at least one checkpoint between point a and b to make
ccpat a satisfy RDT for all entire-causal, and TDV on-line RDT protocols.
Lemma 2: If a forced checkpoint is taken between point c and b in Process P 3 , Process P 2
must take another forced checkpoint to satisfy RDT for all entire-causal, and TDV on-line
RDT protocols.
ccpat c ccpat a
initial checkpoint m 4
a c b

Figure

5: The checkpoint and communication patterns ccpat a and ccpat c .
forced checkpoint is taken between point c and b in Process P 3 , the Z-path
becomes a non-causally doubled PCM-path since m 3 turns out prime. Hence P 2
has to force another checkpoint to break this PCM-path to satisfy RDT for all entire-causal,
and TDV on-line RDT protocols, as the scenario shown in Figure 3 (a). Q.E.D.
We now consider the following theorem.
Theorem 2: There is no optimal on-line protocol based on the entire causal history in terms
of the number of forced checkpoint.
protocol is optimal if and only if given any checkpoint and communication pat-
tern, no other protocol has less number of forced checkpoints than it. See the checkpoint
and communication pattern ccpat a depicted in Figure 5. Since the protocol CPm in Counterexample
needs only one forced checkpoint to make ccpat a satisfy RDT, protocols that
force any checkpoint between point c and b (by Lemma 2 these protocols must force two
checkpoints), and protocols that take more than one checkpoint between point a and c cannot
be optimal. So an optimal protocol, if any, must take exactly one forced checkpoint
between point a and c according to Lemma 1. However, such an on-line protocol cannot be
optimal because it has to force one checkpoint in the cut pattern ccpat c , shown as the left
region of the dotted line in Figure 5, due to the same causality with that in ccpat a at the
same position. But the protocol CPn in Counterexample 1 takes zero forced checkpoint in
ccpat c . Therefore, there is no optimal on-line protocol based on the entire causal history in
terms of the number of forced checkpoints. Q.E.D.
As mentioned earlier in Counterexample 1, both the protocols CPm and CPn only
piggyback the transitive dependency vector. Hence we can have the corollary below with
the similar proof of the previous theorem.
Corollary 2: There is no optimal on-line protocol based on the transitive dependency
tracking (TDV) in terms of the number of forced checkpoints.
4. Techniques of Comparison
4.1 FDAS vs Other Protocols
Wang proposed the Fixed-Dependecy-After-Send (FDAS) checkpointing protocol in [8],
that breaks all PCM-conditions. In this subsection, two assertions that FDAS outperforms
protocols which force a checkpoint at weaker conditions than FDAS's, and that protocols
which force a checkpoint at stronger conditions are better than FDAS, both in terms of the
number of forced checkpoints, are demonstrated. First we prove that the former assertion
is true. Let C f denotes the condition on which FDAS is based (i.e. breaking all PCM-
conditions), and CPw denotes a protocol which takes a forced checkpoint at a weaker
condition than FDAS's, with its based condition denoted Cw . Obviously C f is a subset of Cw
and we represent this relation as C f ) Cw . Let ccpat f and ccpat w represent the checkpoint
and communication patterns produced by the protocols FDAS and CPw respectively. Since
adding forced checkpoints cannot make any PC-path (i.e. prime causal path) in the original
checkpoint and communication pattern become a non-PC path, we directly have the following
lemma.
Lemma 3: For any PC-path in the original checkpoint and communication pattern, it is
still a PC-path in the checkpoint and communication pattern produced by any protocol.
Now we define an extra PC-path as a non-PC path originally but becoming a PC-path
due to the forced checkpoint taken by a protocol. We then have the following two lemmas.
Lemma 4: For any extra PC-path in ccpat f , it is also an extra PC-path in ccpat w .
Proof: Assume there exists an extra PC-path - in ccpat f which is not an extra PC-path in
ccpat w . An extra PC-path is produced only when a forced checkpoint is taken before it. Thus
there exists a PC-path condition - 1 before send(-:first) in ccpat f such that FDAS forced
the process to take a checkpoint to break the C f condition formed by - 1 , and this checkpoint
made - become an extra PC-path. We then say that - is produced by - 1 . Obviously, - 1 is in
the causal past of -. Similarly, - 1 is a PC-path either because itself is originally a PC-path

Figure

The observation process in Lemma 4.
or because it is an extra PC-path produced by another PC-path - 2 , which is in the causal
past of - 1 and thus also in the causal past of -. By repeatedly the foregoing observation,
and since messages in the causal past of - is finite, eventually we can obtain an original
PC-path - n . The previous progress is shown in Figure 6. By Lemma 3, - n is also a PC-path
in ccpat w . Hence CPw must force the process to take a checkpoint (not necessarily the
same checkpoint with the one in ccpat f ) between receive(- n :last) and its nearest previous
message-sending event to avoid - n to form a C f condition that CPw also needs to break
since C f ) Cw . The forced checkpoint makes - n\Gamma1 in ccpat w become an extra PC-path since
- in ccpat f is also an extra PC-path and there is no other message-sending event between
receive(- n :last) and its nearest previous message-sending event (namely there cannot exist
a causal path that prevents - n\Gamma1 from becoming prime). For the same reason, - n\Gamma2 also
becomes a PC-path in ccpat w , and finally - also becomes an extra PC-path in ccpat w . This
leads to a contradiction. Q.E.D.
Lemma 5: FDAS can never force two consecutive checkpoints between two consecutive
Condition C w (if any)
PC-path PC-path

Figure

7: The scenario of Lemma 5.
checkpoints forced by CPw.
Proof: We prove this lemma by showing that CPw must force at least one checkpoint between
any two consecutive forced checkpoints taken by FDAS. See the scenario shown in

Figure

7, there are two consecutive checkpoints forced by FDAS, so there exist two continuous
conditions. For the PC-path of the latter C f condition in ccpat f , by Lemma 3
and Lemma 4, it is also a PC-path in ccpat w . Therefore CPw has to force one checkpoint
between this PC-path and its nearest previous message-sending event to prevent a C f condition
from being formed, shown as the hollow diamond in Figure 7. This checkpoint is
obviously between the two consecutive checkpoints forced by FDAS. Q.E.D.
As a consequence, we can derive the following "monotonicity " property.
Theorem 3: CPw takes the n-th forced checkpoint no later than FDAS does, for all n.
Proof: By induction, because the given checkpoint and communication pattern are exactly
the same for CPw and FDAS before any forced checkpoint is taken, it is clear that CPw
must force the first checkpoint no later than FDAS does for the reason that C f ) Cw . Now
suppose CPw takes the k-th checkpoint no later than FDAS does, according Lemma 5, we
have that CPw will take the 1)-th checkpoint no later than FDAS does. Q.E.D.
Let #f ckpt(CP) denotes the number of forced checkpoints taken by the protocol CP.
Applying the previous theorem, it is obvious that #f ckpt(CPw) - #f ckpt(FDAS). The
Russell's algorithm [19] and the protocol presented in [20], that are named No-Receive-
After-Send (NRAS) and Fixed-Dependency-Interval (FDI) by Wang in [8] respec-
tively, are both RDT protocols. By their definitions, NRAS breaks all CM-paths and FDI
forces a checkpoint whenever a PC-path is encountered. Hence they belong to the family of
CPw. By Theorem 3, we know that FDAS is better than these two protocols in terms of
the number of forced checkpoints.
Here we begin to demonstrate that the latter assertion aforementioned in the very beginning
is valid. Also, let CPs denote a protocol which takes a forced checkpoint at a stronger
condition than FDAS's, and the condition it based is C s , obviously where C s ) C f . Let
ccpat s represent the checkpoint and communication pattern produced by the protocol CPs.
Similarly we consider the following lemma.
Lemma For any extra PC-path in ccpat s , it is also an extra PC-path in ccpat f .
Proof: Assume there exists an extra PC-path - in ccpat s , which is not an extra PC-path in
ccpat f . Since CPs also only breaks some certain PCM-conditions, by the same observation
with Lemma 4, we can obtain an original PC-path - n , that causes - to become an extra
PC-path. By Lemma 3, - n is also a PC-path in ccpat f . Hence FDAS must force the process
to take a checkpoint (not necessarily the same checkpoint with the one in ccpat s ) between
receive(- n :last) and its nearest previous message-sending event to avoid - n to form a C f
condition that FDAS needs to break. The forced checkpoint makes - n\Gamma1 in ccpat f become
an extra PC-path since - n\Gamma1 in ccpat s is also an extra PC-path and there is no other message-sending
event between receive(- n :last) and its nearest previous message-sending event. For
the same reason, - n\Gamma2 also becomes a PC-path in ccpat f , and finally - also becomes an extra
PC-path in ccpat f . This leads to a contradiction. Q.E.D.
With the similar description of Lemma 5, the following lemma can be proved.
Lemma 7: CPs can never force two consecutive checkpoints between two consecutive
checkpoints forced by FDAS.
Therefore we can obtain the corollary below in a straightforward way.
Corollary 3: FDAS takes the n-th checkpoint no later than CPs does, for all n.
And so, the assertion #f ckpt(FDAS) - #f ckpt(CPs) holds. The RDT protocol
BHMR proposed in [14] breaks non-visibly doubled PCM-paths and some PCM-cycles
(including all non-doubled PCM-cycles), and thus it belongs to the family of CPs. As a side
effect of the foregoing corollary, we give a formal proof showing that BHMR outperforms
FDAS in terms of the number of forced checkpoints, instead of the simulation results in
4.2 No-PCM-Cycle vs FDAS
Another interesting result is the technique for comparing No-PCM-Cycle and FDAS.
Applying Corollary 3, the protocol No-PCM-Cycle that breaks non-visibly doubled PCM-
paths and all PCM-cycles outperforms FDAS because its based condition is stronger than
FDAS's. However we find that No-PCM-Cycle is actually equivalent to the protocol
FDAS, shown in the following theorem.
Theorem 4: If all PCM-cycles and non-visibly doubled PCM-paths are broken in the check-point
and communication pattern, any visibly doubled PCM-path is also broken.
Proof: For a visibly doubled PCM-path - \Delta m shown in Figure 8 (a), since there must exist a
prime path that visibly doubles - \Delta m, without loss of generality, - 1 can be assumed prime.
From

Figure

8 (a), we know that - 1 is in the causal past of -:last. Now we show by a case
analysis that - \Delta m will be broken.
(a). If - 1 \Delta (-:last) is prime, the PCM-cycle - 1 \Delta (-:last) \Delta m is broken, and thus the PCM-path
(b). If - 1 \Delta (-:last) is not prime, there exists a causal path - 0
1 to process P i , which is necessarily
before receive(- 1 :last) (otherwise - will turn out non-prime), as shown in Figure 8
(a). Without lost of generality, we assume - 0
1 to be the nearest causal path to P i before
1 :first) is a PCM-condition. If this PCM-condition is broken
by the theorem assumption, the forced checkpoint will make - 1 \Delta (-:last) become prime
since is the first causal path to P i after receive(- 1 :last), and consequently the
will be broken. If not, the PCM-path
1 :first) is a visibly doubled
PCM-path, shown as Figure 8 (b). Clearly, - 2 is in the causal past of - 1 :last and thus in
the causal past of - 1 (also in the causal past of -:last). By repeatedly applying the foregoing
observation, and since messages in the causal past of -:last is finite, eventually we
can obtain a PCM-condition - n \Delta (- 0
n :first), which is either a non-visibly doubled PCM-path
or a PCM-cycle and therefore both need to be broken. The forced checkpoint will make
become prime and the PCM-path -
will be broken. With
the same reason, - n\Gamma2 \Delta (- 0
n\Gamma2 :first) will be also broken and finally the PCM-path - \Delta m will
also be broken. Q.E.D.
According to the previous theorem, we have that the protocol No-PCM-Cycle in fact
breaks all PCM-conditions, so it is equivalent to FDAS. This result shows that we can
'.first
.last
(a) (b)

Figure

8: The scenario of Theorem 4.
reduce the redundant size of piggybacked control information by adopting FDAS instead of
No-PCM-Cycle because No-PCM-Cycle needs extra information to distinguish a visibly
doubled PCM-path.
4.3 PCM vs PESCM
In [15], Baldoni et. al. proposed a more constrained characterization of the RDT property,
PESCM , for designing protocols. A PESCM-condition is composed of a PCM-condition - \Delta m
such that - is elementary and simple besides being prime. The interest of this subsection
lies in the fact that the existence of a PCM-condition implies the existence of a PESCM-
condition at the same position. It consequently becomes unnecessary to take such a stronger
condition with more piggybacked control information into consideration for some protocols.
First, we introduce the definitions of the terms "elementary" and "simple" [15].
Definition 7: A Z-path - is elementary if its traversal sequence P
is the sequence of processes traversed by -, has no repetition.
Definition 8: A causal path simple if the two events receive(m i )
and send(m i+1 ) occur in the same interval, 8i (1
Namely, an elementary Z-path only traverses a process once, and a simple causal path
does not include local checkpoints. For instance, in the checkpoint and communication
pattern shown in Figure 1, the path [m neither elementary nor simple because it
traverses process P j twice and the local checkpoint C k;1 is included. But the path [m
is both elementary and simple.
By Definition 7, we have that every causal path contains an elementary causal path. The
elementary causal path contained by a prime causal path - has the same starting interval
and ending point with - and thus is also prime. A PECM-condition is defined as a PCM-
condition with the property that - is elementary in addition to being prime. Then we
directly have the following theorem and corollary.
Theorem 5: The existence of a PCM-condition implies the existence of a PECM-condition
at the same position.
Corollary 4: The existence of a non-doubled PCM-condition implies the existence of a
non-doubled PECM-condition at the same position.
Next we begin to demonstrate the lemma below.
Lemma 8: A PEC-path (prime and elementary causal path) contains a PESC-path (prime,
elementary and simple causal path).
Proof: Note that a non-simple causal path - can be written as each
component - i is simple. We prove this lemma by showing that the last simple path contained
by a PEC-path is prime (of course is elementary). As depicted in Figure 9, a PEC-path
l is not prime, then there exists
a prime path - from point x 0 to point y 0 , where point y 0 precedes point y. Since - 1
is a causal path with receive(-:last) hb
turns out non-prime. This leads
to a contradiction. Q.E.D.
According to Theorem 5, Corollary 4 and the previous lemma, it can be easily verified
that the following theorem and corollary are true.
Theorem 6: The existence of a PCM-condition implies the existence of a PESCM-condition
at the same position.
Corollary 5: The existence of a non-doubled PCM-condition implies the existence of a
non-doubled PESCM-condition at the same position.
The idea underlying the previous results is that the protocol No-PESCM that breaks
all PESCM-conditions and the protocol No-Non-Visibly-Doubled-PESCM that breaks
non-visibly doubled PESCM-paths and non-doubled PESCM-cycles presented in [15] are exactly
the same with FDAS and NNVD-PCM respectively, however with more piggybacked
control information for the sake of necessity to distinguish simple paths. Intuitively, we have
to break all non-doubled PCM-conditions in order to satisfy RDT by Theorem 1. Why can

Figure

9: The PEC-path
we achieve this goal only by breaking non-doubled PESCM-conditions in a scenario that
there is not necessarily a PESCM-condition before a PCM-condition such that breaking the
former can eliminate the latter? The reason is because the previous results hold.
5. A Family of RDT Protocols

Figure

depicts a hierarchy graph of comparing a family of communication-induced check-pointing
protocols satisfying the RDT property. A plain arrow from a protocol CP1 to
another protocol CP2 indicates that #f ckpt(CP1) - #f ckpt(CP2) and a dotted arrow
indicates that the piggybacked control information of CP1 is less than that of CP2.
The line with two arrows means "equivalent " and the line with a mark "X" on it means
"incomparable". For the protocol CBR (Checkpoint-Befoe-Receive) [8] at the bottom
of

Figure

10, a checkpoint is placed before every message-receiving event. It can be easily
verified that both FDI and NRAS force fewer number of checkpoints than CBR. Figure 10
marshals the discussions in the previous sections. Note that this family includes many existing
RDT protocols in the literature. Therefore the result is helpful for a wide range of
practical applications.
No-PCM-Path
No-PCM-Circle
FDAS
NRAS FDI
CBR

Figure

10: Comparing a family of RDT protocols.
6. Conclusions
This paper has provided a theoretical analysis for RDT protocols. In the context, some
"impossibility " problems are addressed. First, we have shown that the common intuitions
in the literature are not convincing and it definitely needs to a formal proof to demonstrate
that one protocol is better than another one. Through rigorous demonstrations, we usually
found that it is not necessarily worthy to adopt protocols based on stronger conditions with
more piggybacked control information. We also proved that there is no optimal on-line
protocol that ensures the RDT property. This scenario is quite common in the area of on-line
algorithms due to no knowledge of future information. Moreover, some techniques for
comparing useful protocols have been proposed. We showed that these techniques can be
exploited to compare many existing protocols in the literature. Hence our results provide
guidelines for designing and evaluating efficient communication-induced checkpointing RDT
protocols.

Acknowledgements

The authors wish to express their sincere thanks to Jean-Michel Helary (IRISA) and Michel
Raynal (IRISA) whose comments helped improve the presentation of the paper. We would
like also to thank Jeff Westbrook for his valuable discussions about on-line algorithms. Tsai
and Kuo's work are supported by the National Science Council, Taiwan, ROC, under Grant
NSC 87-2213-E-259-007.



--R

"Consistent global checkpoints based on direct dependency tracking,"
"Distributed snapshots: determining global states of distributed systems,"
"A survey of rollback-recovery protocols in message-passing systems,"
"System structure for software fault-tolerant,"
"Checkpointing and rollback-recovery for distributed systems,"
"Experimental evaluation of multiprocessor cache-based error recovery,"
"Necessary and sufficient conditions for consistent global snapshots,"
"Consistent global checkpoints that contain a given set of local check- points,"
"The maximum and minimum consistent global checkpoints and their applications,"
"Guaranteed deadlock recovery: deadlock resolution with rollback propagation,"
"Checkpointing distributed applications on mobile computers,"
"Causal distributed breakpoints,"
"When piecewise determinism is almost true,"
"A communication-induced checkpointing protocol that ensures rollback-dependency trackability,"
"Rollback-dependency trackability: an optimal characterization and its protocol,"
"Time, clocks and the ordering of events in a distributed system,"
"Efficient distributed recovery using message logging,"
"Optimistic recovery in distributed systems,"
"State restoration in systems of communicating processes,"
"Optimal checkpointing and local recording for domino-free rollback recovery,"
--TR

--CTR
Roberto Baldoni , Jean-Michel Hlary , Michel Raynal, Rollback-dependency trackability: visible characterizations, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.33-42, May 04-06, 1999, Atlanta, Georgia, United States
Jichiang Tsai, On Properties of RDT Communication-Induced Checkpointing Protocols, IEEE Transactions on Parallel and Distributed Systems, v.14 n.8, p.755-764, August
B. Gupta , Z. Liu , Z. Liang, On designing direct dependency: based fast recovery algorithms for distributed systems, ACM SIGOPS Operating Systems Review, v.38 n.1, p.58-73, January 2004
B. Gupta , S. K. Banerjee, A Roll-Forward Recovery Scheme for Solving the Problem of Coasting Forward for Distributed Systems, ACM SIGOPS Operating Systems Review, v.35 n.3, p.55-66, July 1 2001
D. Manivannan , Mukesh Singhal, Quasi-Synchronous Checkpointing: Models, Characterization, and Classification, IEEE Transactions on Parallel and Distributed Systems, v.10 n.7, p.703-713, July 1999
J.-M. Hlary , A. Mostefaoui , R. H. B. Netzer , M. Raynal, Communication-based prevention of useless checkpoints in distributed computations, Distributed Computing, v.13 n.1, p.29-43, January 2000
Jun-Lin Lin , Margaret H. Dunham, A Low-Cost Checkpointing Technique for Distributed Databases, Distributed and Parallel Databases, v.10 n.3, p.241-268, December 2001
communication-induced protocols;checkpointing;rollback recovery;rollback-dependency trackability;on-line algorithms