An analysis of communication induced checkpointing
Published 20 January 2003
Lorenzo Alvisi, E. N. Mootaz Elnozahy, S. Rao, Shahid Husain, A. de Mel
Citations131
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
There is sufficient evidence to suspect that much of the conventional wisdom about these protocols is questionable, according to a prototype implementation and validated simulations of communication induced checkpointing.
Abstract
Communication induced checkpointing (CIC) allows processes in a distributed computation to take independent checkpoints and to avoid the domino effect. This paper presents an analysis of CIC protocols based on a prototype implementation and validated simulations. Our result indicate that there is sufficient evidence to suspect that much of the conventional wisdom about these protocols is questionable.
Keywords
Computer Science
Communications of the ACMTime, clocks, and the ordering of events in a distributed system
8,437 Citations1978Leslie Lamport
A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events, and a bound is derived on how far out of synchrony the clocks can become.
ACM Transactions on Computer SystemsDistributed snapshots
2,439 Citations1985K. Mani Chandy, Leslie Lamport
ACM Computing SurveysA survey of rollback-recovery protocols in message-passing systems
1,795 Citations2002E. N. Mootaz Elnozahy, Lorenzo Alvisi +2 more
This survey covers rollback-recovery techniques that do not require special language constructs and distinguishes between checkpoint-based and log-based protocols, which rely solely on checkpointing for system state restoration.
Libckpt: transparent checkpointing under Unix
579 Citations1995James S. Plank, Micah Beck +2 more
The performance of consistent checkpointing
355 Citations2003E. N. Mootaz Elnozahy, David B. Johnson +1 more
It is argued that these measurements show that consistent checkpointing is an efficient way to provide fault tolerance for long-running distributed applications.
IEEE Transactions on Parallel and Distributed SystemsNecessary and sufficient conditions for consistent global snapshots
239 Citations1995Robert H. B. Netzer, Jian Xu
This work proves the exact conditions for an arbitrary checkpoint, or a set of checkpoints, to belong to a consistent global snapshot, a previously open problem.
Generalized communicators in the Message Passing Interface
215 Citations2002Ian Foster, Carl Kesselman +1 more
Extensions to the Message Passing Interface (MPI) are proposed that generalize the MPI communicator concept to allow multiple communication endpoints per process, dynamic creation of endpoints, and the transfer of end points between processes.
Global checkpointing for distributed programs
132 Citations2003L.M.E. Silva, Juliana Galvão da Silva
A novel algorithm for checkpointing and rollback recovery in distributed systems is presented that includes the damage assessment phase, unlike previous schemes that either assume that an error is detected immediately after it occurs (fail-stop) or simply ignore the damage caused by imperfect detection mechanisms.
Frontiers in Digital HealthA Distributed Domino-effect free Recovery Algorithm
120 Citations1984D. Briatico, Augusto Ciuffoletti +1 more
CATCH - Compiler-Assisted Techniques for Checkpointing
108 Citations2005Chung‐Chi Jim Li, W.K. Fuchs
A compiler-based approach to generating efficient checkpoints for process recovery is described, and a heuristic algorithm has been developed to obtain a quick suboptimal solution.
On the use and implementation of message logging
103 Citations2002E. N. Mootaz Elnozahy, Willy Zwaenepoel
A number of experiments are presented showing that for compute-intensive applications executing in parallel on clusters of workstations, message logging has higher failure-free overhead than coordinated checkpointing, but result in much shorter output latency thancoordinated checkpointing.
Faster checkpointing with N+1 parity
95 Citations2002James S. Plank, Kai Li
A basic algorithm is described that uses two extra processors for checkpointing and enables the system to tolerate any single processor failure and the algorithm's speed comes from a combination of N+1 parity, extra physical memory, and virtual memory hardware so that checkpoints need not be written to disk.
Optimistic message logging for independent checkpointing in message-passing systems
75 Citations2003Yueqi Wang, W.K. Fuchs
A periodic independent checkpointing scheme with optimistic logging to reduce performance degradation during normal execution while keeping the recovery cost acceptable is described.
Egida: an extensible toolkit for low-overhead fault-tolerance
73 Citations2003S. Rao, Lorenzo Alvisi +1 more
The design and implementation of Egida, an object-oriented toolkit designed to support transparent rollback-recovery, are discussed and the MPICH implementation of the MPI standard is integrated.
Information Processing LettersOptimal checkpointing and local recording for domino-free rollback recovery
69 Citations1987K. Venkatesh, T. Radhakrishnan +1 more
A technique is developed which selectively stores the received messages in order to account for the backward dependencies and which coordinates the checkpoints to eliminate the retransmission dependencies, thus achieving domino-free rollback.
Preventing useless checkpoints in distributed computations
60 Citations2002Jean-Michel Hélary, Achour Mostéfaoui +2 more
A general and efficient protocol answering the following important problem is proposed: given a set of processes that take (basic) local checkpoints in an independent and unknown way, to design a communication induced checkpointing protocol that directs processes to take additional local (forced) checkpoints to ensure that no local checkpoint is useless.
CATCH-compiler-assisted techniques for checkpointing
60 Citations2002C.-C.J. Li, W.K. Fuchs
A compiler-based approach to generating efficient checkpoints for process recovery is described, and a heuristic algorithm has been developed to obtain a quick suboptimal solution.
RENEW: a tool for fast and efficient implementation of checkpoint protocols
37 Citations2002Nuno Neves, W.K. Fuchs
Three distinct classes of protocols were evaluated using the RENEW environment with SPEC and NAS benchmarks on a network of workstations connected by ATM and it was observed that the communication-induced protocol emulated the behavior of the coordinated protocol, with comparable performance.
A VP-accordant checkpointing protocol preventing useless checkpoints
36 Citations2002Roberto Baldoni, Francesco Quaglia +1 more
A communication-induced checkpointing protocol is presented that avoids useless checkpoints by preventing on-the-fly the formation of suspect Z-cycles and its performance with respect to other protocols is discussed.
Lecture notes in computer scienceVirtual precedence in asynchronous systems: Concept and applications
29 Citations1997Jean-Michel Hélary, Achour Mostéfaoui +1 more
It is shown that the VP property encompasses logical clocks systems and communication-induced checkpointing protocols, and a new and efficient protocol which ensures no local checkpoint is useless is derived from P.
Integrating checkpointing with transaction processing
20 Citations2002Y.M. Wang, Pi-Yu Chung +2 more
This work describes a way of integrating check-pointing with transactions to ensure consistency and recoverability of data stored outside the databases.
An object-oriented testbed for the evaluation of checkpointing and recovery systems
15 Citations2002Bina Ramamurthy, Shambhu Upadhyaya +1 more
The design and development of an object-oriented testbed for simulation and analysis of checkpointing and recovery schemes in distributed systems and its implementation as an extension of DEPEND provides for unique system-level dependability analysis under realistic fault conditions unlike existing simulation tools.
Lecture notes in computer sciencePerformance of consistent checkpointing in a modular operating system: Results of the FTM experiment
12 Citations1994Gilles Muller, Mireille Hue +1 more
It is argued that checkpointing can be integrated into a modular micro-kernel based operating system without degradation of the system performances.