An Index-Based Checkpointing Algorithm for Autonomous Distributed Systems.
AbstractThis paper presents an index-based checkpointing algorithm for distributed systems with the aim of reducing the total number of checkpoints while ensuring that each checkpoint belongs to at least one consistent global checkpoint (or recovery line). The algorithm is based on an equivalence relation defined between pairs of successive checkpoints of a process which allows us, in some cases, to advance the recovery line of the computation without forcing checkpoints in other processes. The algorithm is well-suited for autonomous and heterogeneous environments, where each process does not know any private information about other processes and private information of the same type of distinct processes is not related (e.g., clock granularity, local checkpointing strategy, etc.). We also present a simulation study which compares the checkpointing-recovery overhead of this algorithm to the ones of previous solutions.
Introduction
Checkpointing is one of the techniques for providing
fault-tolerance in distributed systems [6]. A global check-point
consists of a set of local checkpoints, one for each pro-
cess, from which a distributed computation can be restarted
after a failure. A local checkpoint is a state of a process
saved on stable storage. A global checkpoint is consistent
if no local checkpoint in that set happens before [9] another
one [4, 10].
Three classes of algorithms have been proposed in the
literature to determine consistent global checkpoints: un-
coordinated, coordinated and communication induced [6].
In the first class, processes take local checkpoints independently
on each other and upon the occurrence of a failure,
a procedure of rollback-recovery tries to build a consistent
global checkpoint. Note that, a consistent global checkpoint
might not exist producing a domino effect [1, 12] which, in
the worst case, rollbacks the computation to its initial state.
In the second class, an initiator process forces other pro-
cesses, during a failure-free computation, to take a local
This work is partially supported by Scientific Cooperation Net-work
of the European Community "OLOS" under contract No.
ERB4050PL932483.
checkpoint by using control messages. The coordination
can be either blocking [4] or non-blocking [8]. However, in
both cases, the last local checkpoint of each process belongs
to a consistent global checkpoint.
In the third class, the coordination is done in a lazy
fashion by piggybacking control information on application
messages. Communication-induced checkpointing algorithms
can be classified in two distinct categories: model-based
and index-based [6]. Algorithms in the first cate-
gory, for example [2, 14], have the target to mimic a piece-wise
deterministic behavior for each process [7, 13] as well
as providing the domino-free property. Index-based algorithms
associate each local checkpoint with a sequence
number and try to enforce consistency among local checkpoints
with the same sequence number [3, 5, 11]. Index-based
algorithms ensure domino-free rollback with, gener-
ally, less overhead, in terms of number of checkpoints and
control information, than model-based ones.
In this paper we present an index-based checkpointing
protocol that reduces the checkpointing overhead in terms
of number of checkpoints compared to previous index-based
algorithms. Our protocol is well suited for autonomous
environments where each process does not have
any private information of other processes.
To design our algorithm, we extract the rules, used by
index-based algorithms, to update the sequence number.
This points out that checkpoints are due to the process of
increasing of the sequence numbers. Hence, we derive an
algorithm that, by using an equivalence relation between
pair of successive checkpoints of a process, allows a recovery
line to advance without increasing its sequence number.
In the worst case, our algorithm takes the same number of
checkpoints as in [11]. The advantages of our algorithm are
quantified by a simulation study showing that the check-pointing
overhead can be reduced up to 30% compared to
the best previous solution. The price we pay is that each
application message piggybacks more control information
(one vector of integers) compared to previous proposals.
The paper is organized as follows. Section 2 presents the
system model. Section 3 shows the class of index-based
checkpointing algorithms in the context of autonomous en-
vironments. Section 4 describes the equivalence relation
and the proposed algorithm. In Section 5 a simulation study
is presented.
2. Model of the Distributed Computation
We consider a distributed computation consisting of n
which interact by messages ex-
changing. Each pair of processes is connected by a two-
ways reliable channel whose transmission delay is unpredictable
but finite.
are autonomous in the sense that: they do not
share memory, do not share a common clock value 1 and do
not have access to private information of other processes
such as clock drift, clock granularity, clock precision and
speed. Recovery actions due to process failures are not considered
in this paper.
A process produces a sequence of events; each event
moves the process from one state to another. We assume
events are produced by the execution of internal, send or
receive statements. Moreover, for simplicity, we consider
a checkpoint C as a particular type of internal event of a
process, which dumps the current process state onto stable
storage. The send and receive events of a message m
are denoted respectively with send(m) and receive(m). A
distributed execution -
can be modeled as a partial order of
events -
is the set of all events and !
is the happened-before relation [9].
A checkpoint in process P i is denoted as C i;sn where sn
is called the index, or sequence number, of a checkpoint.
Each process takes checkpoints either at its own pace (ba-
sic checkpoints) or induced by some communication pattern
(forced checkpoints). We assume that each process P i takes
an initial basic checkpoint C i;0 and that, for the sake of sim-
plicity, basic checkpoints are taken by a periodic algorithm.
We use the notation next(C i;sn ) to indicate the successive
checkpoint, taken by P i , after C i;sn . A checkpoint interval
I i;sn is the set of events between C i;sn and next(C i;sn ).
message m sent by P i to P j is called orphan with
respect to a pair (C i;sn its receive event occurred
before C j;sn j while its send event occurred after
checkpoint C is a set of local checkpoints
one for each process. A global
checkpoint C is consistent if no orphan message exists in
any pair of local checkpoints belonging to C. In the fol-
lowing, we denote with C sn a global checkpoint formed by
checkpoints with sequence number sn 2 .
1 The index-based algorithm presented in [5] assumes, for example, a
standard clock synchronization algorithm, which provides a common clock
value to each process.
We use the term consistent global checkpoint Csn and recovery line
Lsn interchangeably.
3. Index-based Checkpointing Algorithms
The simplest way to form a consistent global checkpoint
is, each time a basic checkpoint C i;sn is taken by process
to start an explicit coordination. This coordination results
in a consistent global checkpoint C sn associated to that
local checkpoint. This strategy induces checkpoints
(one for each process) per basic checkpoint.
Briatico at al. [3] argued that the previous "centralized"
strategy can be "decentralized" in a lazy fashion by piggy-backing
on each application message m the index sn of the
last checkpoint taken (denoted m:sn).
Let us assume each process P i endows a variable sn i
which represents the sequence number of the last check-
point. Then, the Briatico-Ciuffoletti-Simoncini (BCS) algorithm
can be sketched by using the following rules associated
with the action to take a local checkpoint:
When a basic checkpoint is scheduled, sn i is increased by
one and a checkpoint C i;sn i is taken;
Upon the receipt of a message m, if sn
checkpoint Ci;m:sn is taken and sn i is set to m:sn, then the message is
processed.
By using the above rules, it has been proved that
C sn is consistent [3]. Note that, due to the rule
take-forced(BCS), there could be some gap in the index
assigned to checkpoints by a process. Hence, if a process
has not assigned the index sn, the first local checkpoint
of the process with sequence number greater than sn can be
included in the consistent global checkpoint C sn .
In the worst case of BCS algorithm, the number of forced
checkpoints induced by a basic one is n \Gamma 1. In the best case,
if all processes take a basic checkpoint at the same physical
time, the number of forced checkpoints per basic one
is zero. However, in an autonomous environment, local indices
of processes may diverge due to many causes (process
speed, different period of the basic checkpoint etc). This
pushes the indices of some processes higher and each time
one of such processes sends a message to another one, it is
extremely likely that a number of forced checkpoints, close
to will be induced.
To reduce the number of checkpoints, an interesting observation
comes from the Manivannan-Singhal algorithm
[11] which has been designed for non-autonomous distributed
systems. There is no reason to take a basic check-point
if at least one forced checkpoint has been taken during
the current checkpoint interval. So, let us assume process
indicates if at least one
forced checkpoint is taken in the current checkpoint period
(this flag is set to FALSE each time a basic checkpoint is
scheduled, and set to TRUE each time a forced checkpoint
is taken). A version of Manivannan-Singhal (MS) algorithm
well suited for autonomous environment can be sketched by
the following rules:
When a basic checkpoint is scheduled, if skip
then increased by one and a checkpoint
Upon the receipt of a message m, if sn i ! m:sn then a
checkpoint Ci;m:sn is taken, sn i is set to m:sn and skip
the message is processed.
Even though MS algorithm produces a reduction
of the total number of checkpoints, the number of
forced checkpoints caused by a basic one is equal
to BCS as take-forced(MS) is actually similar to
take-forced(BCS).
In this section we propose an algorithm that includes the
take-basic(MS) rule, however, when a basic check-point
is taken, the local sequence number is updated only
if there was the occurrence of a particular checkpoint and
communication pattern. The rationale behind this solution
is that each time a basic checkpoint is taken without increasing
the sequence number, it does not force checkpoints and
this reduces the total number of checkpoints. At this end, let
us first introduce a relation of equivalence defined on pairs
of successive checkpoints of a process.
4.1. Equivalence Relation Between Checkpoints
Definition 4.1
Two local checkpoints C i;sn and next(C i;sn ) of process P i
are equivalent with respect to the recovery line L sn , denoted
Lsn
Lsn
sn
sn
I 2;sn

Figure

1. Examples of pairs of equivalent
checkpoints.
As an example, let consider the recovery line L sn depicted
in Figure 1. If in I 2;sn process P 2 executes either
send events or receive events of messages which have been
sent before the checkpoints included in the recovery line
Lsn
recovery line L 0
sn
is created by replacing C 2;sn with next(C 2;sn ) from L sn .

Figure

also shows the construction of the recovery line
sn starting from L 0
sn by using the equivalence between
C 1;sn and next(C 1;sn ) with respect to L 0
sn .
As shown in the above examples, the equivalence relation
has a simple property (see Lemmas 4.1 and 4.2 of Section
Lsn
then the set L 0
fC i;sn g[fnext(C i;sn )g is a recovery line. Hence, the presence
of a pair of equivalent checkpoints allows a process
to locally advance a recovery line without updating the sequence
4.2. Sequence and Equivalence Numbers of a Recovery
line
We suppose process P i owns two local variables: sn i
(sequence number) and en i (equivalence number). The
variable sn i stores the number of the current recovery line.
The variable en i represents the number of equivalent local
checkpoints with respect to the current recovery line (both
sn i and en i are initialized to zero).
Hence, we denote as C i;sn;en the checkpoint of P i with
the sequence number sn and the equivalence number en;
the en ? is also called the index of a check-
point. Thus, the initial checkpoint of process P i will be
denoted as C i;0;0 . The index of a checkpoint is updated according
to the following rule: if C i;sn;en
Lsn
then next(C i;sn;en
C i;sn+1;0 .
Process P i also endows a vector EQ i of n integers. The
j-th entry of the vector represents the knowledge of P i
about the equivalence number of P j with the current sequence
number sn i (thus the i-th entry corresponds to en i ).
EQ i is updated according to the following rule: each
application message m sent by process P i piggybacks the
current sequence number sn i (m:sn) and the current EQ i
vector (m:EQ). Upon the receipt of a message m, if
is updated from m:EQ by taking a
component-wise maximum. If m:sn ? sn i , the values in
m:EQ and m:sn are copied in EQ i and sn i .
Let us remark that the set L
recovery line (a sketch proof of this property is given in
Lemma 4.4). So, to the knowledge of P i , the vector EQ i
actually represents the most recent recovery line with sequence
number sn i .
4.3. Tracking the Equivalence Relation
Upon the arrival of a message m, sent by P j , at P i in
the checkpoint interval I i;sn;en , one of the following three
cases is true:
(m has been sent from the left side of the recovery line
has been sent
from the right side of the recovery line [ 8j C j;sn;EQ i [j] );
been sent from the right side of a
recovery line of which P i was not aware).
According to previous cases, at the time of the check-point
next(C i;sn;en ), in one of the following three
alternatives:
(i) If no message m is received in I i;sn;en that falls in
case 2 or 3, then C i;sn;en
Lsn
next(C i;sn;en ). That equivalence
can be tracked by a process using its local context
at the time of the checkpoint next(C i;sn;en ). Thus
next(C i;sn;en equivalence between
shown in Figure 2, is an example
of such a behavior).
(ii) If there exists a message m which falls in case 3
then C i;sn;en is not equivalent to next(C i;sn;en ) and thus
next(C i;sn;en
(iii) If no message falls in case 3 and there exists at least
a message m received in I i;sn;en which falls in case 2,
then the checkpoint next(C i;sn;en ) is causally related to
one checkpoint belonging to the recovery line formed by
communication pattern is shown in

Figure

where, due to m, C 2;sn;0 ! next(C 1;sn;0 )).
The consequence is that process P i cannot determine,
at the time of taking the checkpoint next(C i;sn;en ), if
Lsn
optimistically
(and provisionally) that C i;sn;en
Lsn
As provisional indices cannot be propagated in the system,
if at the time of the first send event after next(C i;sn;en ) the
equivalence is still undetermined, then next(C i;sn;en
0). Otherwise, the provisional index becomes permanent.

Figure

2 shows a case in which message m 0 brings the information
(encoded in m 0 :EQ) to P 1 (before the sending of
Lsn
and the recovery line was
advanced, by P 2 , from L sn to L 0
sn . In such a case, P 1 can
determine C 1;sn;0 is equivalent to next(C 1;sn;0 ) with respect
to L 0
sn and, then, advances the recovery line to L 00
sn .
4.4. The Algorithm
The checkpointing algorithm we propose (BQF) takes
basic checkpoints by using the take-basic(MS) rule.
However, it does not update the sequence number by optimistically
assuming that a basic checkpoint is equivalent to
the previous one. So we have:
Lsn
sn
sn

Figure

2. Upon the receipt of m 0 , P 1 detects
sn
When a basic checkpoint is scheduled,
If skip i then skip
else en checkpoint Ci;sn;en is taken with
index provisionally set to ! sn
Due to the presence of provisional indices caused by the
equivalence relation, our algorithm needs a rule, when sending
a message, in order to disseminate only permanent indices
of checkpoints.
before sending a message m in I i;sn i ;en i ,
if there has been no send event in I i;sn i ;en i and the index is provisional then
Lsn
then the index ! sn permanent
else sn and the index of the last checkpoint
is replaced permanently with ! sn
the message m is sent;
The last rule of our algorithm take-forced(BQF)
refines BCS's one by using a simple observation. Upon
the receipt of a message m such that m:sn ? sn i , there
is no reason to take a forced checkpoint if there has been
no send event in the current checkpoint interval I i;sn;en . In-
deed, no causal relation can be established between the last
checkpoint C i;sn i ;en i and any checkpoint belonging to the
recovery line L m:sn and, thus, the index of C i;sn i ;en i can
be replaced permanently with the index ! m:sn; 0 ?.
take-forced(BQF): Upon the receipt of a message m in I i;sn i ;en
(a) If sn i ! m:sn and there has been at least a send event in I i;sn i ;en i then
begin
a forced checkpoint Ci;m:sn;0 is taken and its index is permanent;
(b) If sn i ! m:sn and there has been no send event in I i;sn i ;en i then
begin
the index of the last checkpoint C i;sn i ;en i is replaced permanently
the message m is processed;
For example, in Figure 3.a, the local checkpoint
C 3;sn;en3 can belong to the recovery line L sn+1 (so the index
can be replaced with
forced checkpoint
(b)
C3;sn;en 3 C3;sn+1;0
next(C2;sn;en
C3;sn;en 3
(a)

Figure

3. Upon the receipt of m, C 3;sn;en3 can
be a part of L sn+1 (a); C 3;sn;en3 cannot belong
to L sn+1 (b).
the contrary, due to the send event in I 3;sn;en3 depicted in

Figure

3.b, a forced checkpoint with index
has to be taken before the processing of message m.
Point (b) of take-forced(BQF) decreases the number
of forced checkpoints compared to BCS. The else alternative
of send-message(BQF) and the part (a) of
take-forced(BQF), represent the cases in which the
action to take a basic checkpoint leads to update the sequence
number with the consequent induction of checkpoints
in other processes.
Data Structures and Process Behavior. We assume each
process P i has the following data structures:
after first send i , skip i , provisional
past
The boolean variable after first send i is set to TRUE if
at least one send event has occurred in the current check-point
interval. It is set to FALSE each time a checkpoint is
taken.
The boolean variable provisional i is set to TRUE whenever
a provisional index assignement occurs. It is set to
FALSE whenever the index becomes permanent.
present i [j] represents the maximum equivalence number
en j piggybacked on a message m received in the current
checkpoint interval by P i and that falls in the case 2
of Section 4.3. Upon taking a checkpoint or when updating
the sequence number, present i is initialized to -1. If the
checkpoint is basic, present i is copied in past i before its
initialization. Each time a message m is received such that
past past i [j] is set to -1. So, the predicate
past indicates that there is a message
received in the past checkpoint interval that has been sent
from the right side of the recovery line (case 2 of Section
currently seen by P i .
Below the process behavior is shown (the procedures and
the message handler are executed in atomic fashion). This
implementation assumes that there exist at most one provisional
index in each process. So each time two successive
provisional indices are detected, the first index is permanently
replaced with ! sn
init
en i := 0; after first send i := FALSE;
past i [h] := \Gamma1; 8h present i [h] := \Gamma1;
when (m) arrives at P i from
begin
if after first send i then
begin
take a checkpoint C; % forced checkpoint %
after first send i := FALSE;
assign the index ! sn to the last checkpoint C;
provisional i := FALSE; % the index is permanent %
past i [h] := \Gamma1; 8h present i [h] := \Gamma1;
present i [j] := m:EQ[j];
else if
begin
if present i [j] ! m:EQ[j] then present i [j] := m:EQ[j];
8h if past i [h] ! m:EQ[h] then past i [h] := \Gamma1;
process the message m;
when sends data to
if provisional i past
begin
assign the index ! sn to the last checkpoint C;
provisional i := FALSE; % the index is permanent %
past i [h] := \Gamma1; 8h present i [h] := \Gamma1; 8h EQ i [h] := 0;
packet the message %
send (m) to P
after first send i := TRUE;
when a basic checkpoint is scheduled from
if skip i then skip i := FALSE % skip the basic checkpoint
else
begin
if provisional i then % two successive provisional indices %
past
begin
past i [h] := \Gamma1;
assign the index ! sn to the last checkpoint C; % the index is permanent %
else 8h past i [h] := present i [h];
take a checkpoint C; % taking a basic checkpoint
en
assign the index ! sn to the last checkpoint C;
provisional i := TRUE; % the index is provisional %
present i [h] := \Gamma1;
after first send i := FALSE;
4.5. Correctness Proof
Let us first introduce the following simple observations
that derive directly from the algorithm:
Observation 1 For any checkpoint C i;sn;0 , there not
exists a message m with m:sn - sn such that
observation derives from rule
take-forced(BQF) when considering C i;sn;0 is the
first checkpoint with sequence number sn).
Observation 2 For any checkpoint C i;sn;en , there not
exists a message m with m:sn ? sn such that m is
received in I i;sn;en (this observation derives from rule
take-forced(BQF)).
Observation 3 For any message m sent by
derives from the rule send-message(BQF)).
Lemma 4.1 The set
with sn - 0 is a recovery line. If process P i does not
have a checkpoint with index ! sn; 0 ?, the first check-point
must be included in the set
S.
Proof If sn = 0, S is a recovery line by definition. Otherwise
suppose, by the way of contradiction that S is not
a recovery line. Then, there exists a message m, sent by
some process P j to a process P k , that is orphan with respect
to the pair (C j;sn;0 ; C k;sn;0 ). Hence, we have: C
contradicts observation 1.
Suppose process P k does not have a checkpoint with sequence
number sn, in this case, from lemma's assumption,
we replace C k;sn;0 with C k;sn 0 ;0 where sn 0 ? sn. As m
is orphan wrt the pair (C received by
in a checkpoint interval I k;sn 00 ;en such that m:sn ? sn 00
contradicting observation 2.
Suppose process P j does not have a checkpoint with sequence
number sn, in this case, from lemma's assumption,
we replace C j;sn;0 with C j;sn 0 ;0 where sn 0 ? sn. As m
is orphan wrt the pair (C j;sn 0
This contradicts observation 1.
Hence, in all cases the assumption is contradicted and
the claim follows. 2
Lemma 4.2 Let C i;sn;en i and next(C i;sn;en i ) be two local
checkpoints such that C i;sn;en i
Lsn
If the set
with en i - 0, is a recovery line L sn then the set S
is a recovery line.
Proof If C i;sn;en i
Lsn
then from definition
4.1, for each message m sent by P j such that
thus no orphan message can ever exist with respect
to any pair of checkpoints in S 0 . 2
From Lemma 4.1, it trivially follows:
Lemma 4.3 The set L
and 8j EQ i recovery line.
From Lemma 4.1 and Lemma 4.2, we have each check-point
belongs to at least one recovery line. In particular,
belongs to
all recovery lines having sequence number sn 00 such that
Lemma 4.4 The set is a recovery
line.
Proof (Sketch) Let us assume, by the way of contradiction,
S is not a recovery line. If 8j EQ i
the assumption is contradicted. Otherwise, there exists a
message m, sent by some process P j to a process P k , that is
orphan with respect to the pair (C j;sn;EQ i
and there exists a causal message chain - that brings this
information to P i encoded in EQ i . Hence, we have:
upon the arrival
of message m, it falls in case 2 of Section 4.3. In this
case, the index associated to C k;sn;EQk [j] is provisional (see
the third point of Section 4.3). Before P k sends the first
message m 0 forming the causal message chain -, the index
has to be permanent. Hence, according to the algorithm,
the index is replaced by ! sn is reset and
piggybacked on m 0 . As soon as the last message of the
causal message chain m 00 arrives at
which is consistent by lemma 4.3. So the
initial assumption is contradicted and the claim follows. 2
5. A Performance Study
The Simulation Model. The simulation compares BCS,
MS and the proposed algorithm (BQF) in an uniform point-
to-point environment in which each process can send a message
to any other and the destination of each message is a
uniformly distributed random variable. We assume a system
with processes, each process executes internal, send
and receive operations with probability
respectively. The time to execute an operation
in a process and the message propagation time are
exponentially distributed with mean value equal to 1 and 10
time units respectively.
We also consider a bursted point-to-point environment in
which a process with probability enters a burst
state and then executes only internal and send events (with
probability
interval (when we have the uniform point-to-
point environment described above).
Basic checkpoints are taken periodically. Let bcf (basic
checkpoint frequency) be the percentage of the ratio t=T
where t is the time elapsed between two successive periodic
checkpoints and T is the total execution time. For example,
bcf= 100% means that only the initial local checkpoint is a
basic one, while bcf= 0.1% means that each process takes
1000 basic checkpoints.
We also consider a degree of heterogeneity among processes
H . For example, means
all processes have the same checkpoint period
means 25%
(resp. 75%) of processes have the checkpoint period
while the remaining 75% (resp. 25%) has a checkpoint period
A first series of simulation experiments were conducted
by varying bcf from 0:1% to 100% and we measured the
ratio Tot between the total number of checkpoints taken by
an algorithm and the total number of checkpoints taken by
BCS.
In a second series of experiments we varied the degree
of heterogeneity H of the processes and then we measured
the ratio E between the total number of checkpoints taken
by BQF and MS.
As we are interested only in counting how many local
states are recorded as checkpoints, the overhead due to the
taking of checkpoints is not considered. Each simulation
run contains 8000 message deliveries and for each value of
bcf and H , we did several simulation runs with different
seeds and the result were within 4% of each other, thus,
variance is not reported in the plots.
Results of the Experiments. Figure 4 shows the ratio Tot
of MS and BQF in an uniform point-to-point environment.
For small values of bcf (below 1.0%), there are only few
send and receive events in each checkpoint interval, leading
to high probability of equivalence between checkpoints.
Thus BQF saves from 2% to 10% of checkpoints compared
to MS. As the value of bcf is higher than 1.0%, MS and BQF
takes the same number of checkpoints as the probability that
two checkpoints are equivalent tends to zero.
The reduction of the total number of checkpoints is amplified
by the bursted environment (Figure 5) in which the
equivalences between checkpoints on processes running in
the burst mode are disseminated to the other processes causing
other equivalences. In this case, for all values of bcf,
BQF saves from a 7% to 18% checkpoints compared to MS.
Performance of BQF are particularly good in an heterogeneous
environment in which there are some processes
with a shorter checkpointing period. These processes would
push higher the sequence number leading to a very high
checkpointing overhead using either MS or BCS.
In

Figure

6, the ratio E as a function of the degree of heterogeneity
H of the system is shown in the case of uniform
bursted point-to-point environment
The best performance (about 30% less checkpointing than
MS) are obtained when only one
process has a checkpoint frequency ten times greater than
the others) and 2.
In

Figure

7 we show the ratio Tot as a function of bcf
in the case of which is the environment
where BQF got the maximum gain (see Figure 6).
Due to the heterogeneity, bcf is in the range between 1%
and 10% of the slowest processes. We would like to remark
that in the whole range the checkpointing overhead of BQF
is constantly around 30% less than MS.
bcf (% checkpoint period / total execution time)0.20.40.60.8
Tot
total
ckpt
total
ckpt
MS

Figure

4. Tot versus bcf in the uniform point-to-
point environment
bcf (% checkpoint period / total execution time)0.40.8
Tot
total
ckpt
total
ckpt
MS

Figure

5. Tot versus bcf in the bursted point-to-
point environment
6. Conclusion
In this paper we presented an index-based checkpointing
algorithm well suited for autonomous distributed systems
that reduces the checkpointing overhead compared to previous
algorithms. It lies on an equivalence relation that allows
to advance the recovery line without increasing its sequence
number. The algorithm optimistically (and provisionally)
assumes that a basic checkpoint C in a process is equivalent
to the previous one in the same process by assigning
a provisional index. Hence, if at the time of the first send
total
ckpt
total
ckpt
MS)

Figure

in both the uniform
point-to-point environment and the
bursted point-to-point environment
1.0 3.0 5.0 7.0 9.0
bcf (% checkpoint period total execution time)0.600.80Tot
total
ckpt
total
ckpt
MS

Figure

7. Tot versus bcf of the slowest processes
in a bursted point-to-point environment
event after C that equivalence is verified, the provisional index
becomes permanent. Otherwise the index is increased,
as in [3, 11], and this directs forced checkpoints in other
processes.
We presented a simulation study which quantifies the
saving of checkpoints in different environments compared
to previous proposals. The price to pay is each application
message piggybacks information
compared to one integer used by previous algorithms.

Acknowledgements

. The authors would like to thank
Bruno Ciciani, Michel Raynal, Jean-Michel Helary, Achour
Mostefaoui and the anonymous referees for their helpful
comments and suggestions.



--R

On Modeling Consistent Checkpoints and the Domino Effect in Distributed Systems
A Communication-Induced Checkpointing Protocol that Ensures Rollback-Dependency Trackability
A Distributed Domino-Effect Free Recovery Algorithm
Determining Global States of Distributed Systems
A Timestamp-Based Check-pointing Protocol for Long-Lived Distributed Computations
A Survey of Rollback-Recovery Protocols in Message-Passing Systems
Manetho: Transparent Rollback Recovery with Low Overhead
Checkpointing and Rollback-Recovery for Distributed Systems

Finding Consistent Global Checkpoints in a Distributed Computa- tion

System Structure for Software Fault Tolerance
Volatile Logging in n-Fault-Tolerant Distributed Systems
Consistent Global Checkpoints that Contains a Set of Local Checkpoints
--TR

--CTR
D. Manivannan , M. Singhal, Asynchronous recovery without using vector timestamps, Journal of Parallel and Distributed Computing, v.62 n.12, p.1695-1728, December 2002
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
checkpointing;rollback-recovery;performance evaluation;global snapshot;distributed systems;timestamp management;causal dependency;fault tolerance;protocols