A survey of checkpointing algorithms for parallel and distributed computers
---
paper_title: Parallel and Distributed Computing Handbook

paper_content:

Introduction. The High Performance Computing Milieu. Theory, Foundations, Algorithms, Models and Paradigms. Architectures and Technologies. Architectures. Technologies. Tools and Applications, Development Tools. Applications: General Issues. Case Studies. Audience.
---
paper_title: Encyclopedia of Computer Science

paper_content:

From the Publisher: ::: The Encyclopedia of Computer Science is the definitive reference work on computers, computing, and computer science. This new edition has 2,000 pages containing over 600 fully-updated articles by internationally-known computing experts. With its blending of historical perspective and practical reference information, the Encyclopedia of Computer Science is a must-have for every collection. ::: Alphabetically arranged and classified into subject areas, the Encyclopedia will cover the fields of: ::: Hardware Computer systems Information and data Software Mathematics of Computing Theory of computation Methodologies Applications Computing Milieux ::: ::: Features ::: Over 100 entirely new entries Thorough revisions and updates reflecting the latest developments in the field 900 illustrations in black and white, plus full color inserts A list of the 450 contributing international experts, complete with affiliation Thorough cross-references, abbreviations, and acronyms An extensive list of computer science and engineering research journals A timeline of significant computing milestones Ph.D-granting departments of computer science and engineering Glossary of major terms in five languages Key high level languages Numerical tables and constants Articles deleted from the first three editions Over 100 new articles covering emerging, cutting-edge subjects. Examples include: ::: Automated Planning Byte Ordering Cache Coherency Computer Industry: US, Britain, Europe, Japan Computer Ethics Data Mining Database Concurrency Control E-commerce Fuzzy Logic Geographic Information System (GIS) Integer Sequences Legal Issues of the Internet Lyons Electronic Office (LEO) Markup Languages Molecular Computing Multi-agent Systems Partial Evaluation Redundant Array Inexpensive Dish (RAID) Register Allocation Scientific Visualization Simula Telerobotics
---
paper_title: Rollback and Recovery Strategies for Computer Programs

paper_content:

Reliability is an important aspect of any system. On-line diagnosis, parity check coding, triple modular redundancy, and other methods have been used to improve the reliability of computing systems. In this paper another aspect of reliable computing systems is explored. The problem is that of recovering error-free information when an error is detected at some stage in the processing of a program. If an error or fault is detected while a program is being processed and if it cannot be corrected immediately, it may be necessary to run the entire program again. The time spent in rerunning the program may be substantial and in some real time applications critical. Recovery time can be reduced by saving states of the program (all the information stored in registers, primary and secondary storage, etc.) at intervals, as the processing continues. If an error is detected the program is restarted from its most recently saved state. However, a price is paid in saving a state in the form of time spent storing all the relevant information in secondary storage. Hence it is expensive to save the state of the program too often. Not saving any state of the program may cause an unacceptably large recovery time. The problem that we solve is the following. Determine the optimum points at which the state of the program should be stored to recover after any malfunction.
---
paper_title: Necessary and sufficient conditions for consistent global snapshots

paper_content:

Consistent global snapshots are important in many distributed applications. We prove the exact conditions for an arbitrary checkpoint, or a set of checkpoints, to belong to a consistent global snapshot, a previously open problem. To describe the conditions, we introduce a generalization of Lamport's (1978) happened-before relation called a zigzag path. >
---
paper_title: Rollback recovery in distributed systems using loosely synchronized clocks

paper_content:

A rollback recovery scheme for distributed systems is proposed. The state-save synchronization among processes is implemented by bounding clock drifts such that no state-save synchronization messages are required. Since the clocks are only loosely synchronized, the synchronization overhead can be negligible in many applications. An interprocess communication protocol which encodes state-save progress information within message frames is introduced to checkpoint consistent system states. A rollback recovery algorithm that will force a minimum number of nodes to roll back after failures is developed. >
---
paper_title: Time, clocks, and the ordering of events in a distributed system

paper_content:

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
---
paper_title: Distributed snapshots: determining global states of distributed systems

paper_content:

This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.
---
paper_title: Crash recovery with little overhead

paper_content:

Recovering from processor failures in distributed systems is an important problem in the design and development of reliable systems. Two solutions to this problem which involve very little overhead are presented. Without appending any information to the messages of the application program, it is shown that it is possible to recover from failures using O( mod V mod mod E mod ) messages where mod V mod is the number of processors and mod E mod is the number of communication links in the system. The second algorithm can be used to recover from processor failures without forcing nonfaulty processors to roll back under certain conditions. >
---
paper_title: Message-optimal incremental snapshots

paper_content:

The problem of obtaining a global state or snapshot of a distributed processing system is considered. A message-efficient protocol is presented for obtaining incremental snapshots. First, worst-case lower bounds on the number of messages used by any protocol that solves the incremental snapshot problem are given, and then a protocol that is message-efficient is provided. This protocol obtains a snapshot of the system using the most recent snapshot. The message complexity of the incremental snapshot protocol matches the two lower bounds simultaneously, and hence the protocol is asymptotically message optimal. For applications in database systems, debugging distributed programs, monitoring events, or checkpointing, the protocol is asymptotically message optimal. Because of its simplicity, the protocol can be used readily, and since it uses the minimum number of additional messages, the throughput of the distributed system is not adversely affected. >
---
paper_title: Optimal checkpointing and local recording for domino-free rollback recovery

paper_content:

Abstract Backward error recovery or rollback recovery is a well-known technique used in the design of reliable uni-processor computer systems. However, use of this technique for design of reliable distributed computer systems could result in uncontrolled rollback which is known as the domino effect. Here, we formally present the reasons for the domino effect by specifically identifying the unmatched receives (backward dependency) and unmatched sends (retransmission dependency) that occur during reexecution as the sole causes. 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. Rollback is confined only to the interacting processes by dependency tracking of the messages. Further, we present a scheme for identifying and purging possibly contaminated messages during recovery. Our scheme is compared with some of the existing schemes and its significant advantages are highlighted.
---
paper_title: Checkpointing and Rollback-Recovery for Distributed Systems

paper_content:

We consider the problem of bringing a distributed system to a consistent state after transient failures. We address the two components of this problem by describing a distributed algorithm to create consistent checkpoints, as well as a rollback-recovery algorithm to recover the system to a consistent state. In contrast to previous algorithms, they tolerate failures that occur during their executions. Furthermore, when a process takes a checkpoint, a minimal number of additional processes are forced to take checkpoints. Similarly, when a process rolls back and restarts after a failure, a minimal number of additional processes are forced to roll back with it. Our algorithms require each process to store at most two checkpoints in stable storage. This storage requirement is shown to be minimal under general assumptions.
---
paper_title: Rollback recovery in distributed systems using loosely synchronized clocks

paper_content:

A rollback recovery scheme for distributed systems is proposed. The state-save synchronization among processes is implemented by bounding clock drifts such that no state-save synchronization messages are required. Since the clocks are only loosely synchronized, the synchronization overhead can be negligible in many applications. An interprocess communication protocol which encodes state-save progress information within message frames is introduced to checkpoint consistent system states. A rollback recovery algorithm that will force a minimum number of nodes to roll back after failures is developed. >
---
paper_title: An efficient protocol for checkpointing recovery in distributed systems

paper_content:

The authors present an efficient synchronized checkpointing protocol that exploits the dependency relation between processes in distributed systems. In this protocol, a process takes a checkpoint when it knows that all processes on which it computationally depends took their checkpoints, hence the process need not always wait for the decision made by the checkpointing coordinator as in the conventional synchronized protocols. As a result, the checkpointing coordination time is substantially reduced and the possibility of total abort of the checkpointing coordination is reduced. >
---
paper_title: Nonblocking and orphan-free message logging protocols

paper_content:

Currently existing message logging protocols demonstrate a classic pessimistic vs. optimistic tradeoff. It is shown that the optimistic-pessimistic tradeoff is not inherent to the problem of message logging. The authors construct a message-logging protocol that has the positive features of both optimistic and pessimistic protocols: the protocol prevents orphans and allows simple failure recovery; however, it requires no blocking in failure-free runs. Furthermore, this protocol does not introduce any additional message overhead as compared to one implemented for a system in which messages may be lost but processes do not crash.
---
paper_title: A timestamp-based checkpointing protocol for long-lived distributed computations

paper_content:

The authors present a timestamp-based protocol for checkpointing the global state of a long-lived distributed computation in an environment in which processor clocks are approximately synchronized. The protocol is based on periodic checkpointing of local process states and logging of incoming messages during a short bounded interval. It tolerates process crash and performance failures as well as network omission and performance failures. The proposed approach has the advantage of optimistic logging protocols in that it does not require synchronous logging of each message on stable storage. The approach also has the advantage of pessimistic logging protocols in that it avoids the domino effect by recovering to the most recent successful local checkpoint. >
---
paper_title: A crash recovery technique in distributed computing systems

paper_content:

In this paper we propose a new mechanism for implementing checkpoint/rollback-recovery in a distributed computing system. A logical-ring structure is introduced for the maintenance of recovery-related information. Message processing order of a process is maintained by all other processes on its associated ring. It requires no time-consuming operations of writing order information into stable storage. As a result, fail-free overhead is small. When failures occur, only failed processes have to roll back to their latest checkpoints. Surviving processes continue execution without being blocked. Output commit is fast as it needs no synchronization before a message is sent to the outside world. >
---
paper_title: Sender-Based Message Logging

paper_content:

Sender-based message logging, a low-overhead mechanism for providing transparent fault-tolerance in distributed systems, is described. It differs from conventional message logging mechanisms in that each message is logged in volatile memory on the machine from which the message is sent. Keeping the message log in the sender's local memory allows one to recover from a single failure at a time without the expense of synchronously logging each message to stable storage. The message log is then asynchronously written to stable storage, without delaying the computation, as part of the sender's periodic checkpoint. Maintaining the sender-based message log requires at most one extra network packet over non-fault-tolerant reliable message communication and imposes little additional synchronization delay. It can be applied transparently to existing distributed applications and does not required specialized hardware. It is currently being implemented on a network of Sun workstations.
---
paper_title: Optimistic Message Logging for Independent Checkpointing in Message-Passing Systems

paper_content:

Message-passing systems with a communication protocol transparent to the applications typically require message logging to ensure consistency between checkpoints. A periodic independent checkpointing scheme with optimistic logging to reduce performance degradation during normal execution while keeping the recovery cost acceptable is described. Both time and space overhead for message logging can be reduced by detecting messages that need not be logged. A checkpoint space reclamation algorithm is presented to reclaim all checkpoints which are not useful for any possible future recovery. Communication trace-driven simulation for several hypercube programs is used to evaluate the techniques. >
---
paper_title: ON DISTRIBUTED SNAPSHOTS

paper_content:

We develop an efficient snapshot algorithm that needs no control messages and does not require channels to be first-in-first-out. We also show that several stable properties (e.g., termination, deadlock) can be detected with uncoordinated distributed snapshots. For such properties, our algorithm can be further simplified.
---
paper_title: Checkpoint space reclamation for uncoordinated checkpointing in message-passing systems

paper_content:

Uncoordinated checkpointing allows process autonomy and general nondeterministic execution, but suffers from potential domino effects and the associated space overhead. Previous to this research, checkpoint space reclamation had been based on the notion of obsolete checkpoints; as a result, a potentially unbounded number of nonobsolete checkpoints may have to be retained on stable storage. In this paper, we derive a necessary and sufficient condition for identifying all garbage checkpoints. By using the approach of recovery line transformation and decomposition, we develop an optimal checkpoint space reclamation algorithm and show that the space overhead for uncoordinated checkpointing is in fact bounded by N(N+1)/2 checkpoints where N is the number of processes. >
---
paper_title: Checkpointing multicomputer applications

paper_content:

The authors present a checkpointing scheme that is transparent, imposes overhead only during checkpoints, requires minimal message logging, and allows for quick resumption of execution from a checkpointed image. Since checkpointing multicomputer applications poses requirements different from those posed by checkpointing general distributed systems, existing distributed checkpointing schemes are inadequate for multicomputer checkpointing. The proposed checkpointing scheme makes use of special properties of multicomputer interconnection networks to satisfy this set of requirements. The proposed algorithm is efficient both when taking checkpoints and when recovering from checkpointed images. >
---
paper_title: Fault tolerance under UNIX

paper_content:

The initial design for a distributed, fault-tolerant version of UNIX based on three-way atomic message transmission was presented in an earlier paper [3]. The implementation effort then moved from Auragen Systems 1 to Nixdorf Computer where it was completed. This paper describes the working system, now known as the TARGON/32. The original design left open questions in at least two areas: fault tolerance for server processes and recovery after a crash were briefly and inaccurately sketched, rebackup after recovery was not discussed at all. The fundamental design involving three-way message transmission has remained unchanged. However, in addition to important changes in the implementation, server backup has been redesigned and is now more consistent with that of normal user processes. Recovery and rebackup have been completed in a less centralized and thus more efficient manner than previously envisioned. In this paper we review important aspects of the original design and note how the implementation differs from our original ideas. We then focus on the backup and recovery for server processes and the changes and additions in the design and implementation of recovery and rebackup.
---
paper_title: Concurrent robust checkpointing and recovery in distributed systems

paper_content:

A checkpoint/rollback algorithm is presented for multiple processes in a distributed system that uses message passing for communication. Each process in the system can initiate the algorithm autonomously. If only one instance of the algorithm is being executed, the algorithm will force the minimal number of additional processes other than the initiator to make checkpoints (or roll back). The contributions of this research are as follows: (1) the concurrent execution of the algorithm for different global checkpointing instances and rollback instances initiated by several processes is allowed. Deadlocks or livelocks among different global checkpointing instances and rollback instances will not occur; (2) the algorithm is resilient to multiple process failures, and handles network partitioning in a pessimistic way, and (3) the algorithm does not require that messages be received in the order in which they are sent. >
---
paper_title: Checkpointing and Rollback-Recovery for Distributed Systems

paper_content:

We consider the problem of bringing a distributed system to a consistent state after transient failures. We address the two components of this problem by describing a distributed algorithm to create consistent checkpoints, as well as a rollback-recovery algorithm to recover the system to a consistent state. In contrast to previous algorithms, they tolerate failures that occur during their executions. Furthermore, when a process takes a checkpoint, a minimal number of additional processes are forced to take checkpoints. Similarly, when a process rolls back and restarts after a failure, a minimal number of additional processes are forced to roll back with it. Our algorithms require each process to store at most two checkpoints in stable storage. This storage requirement is shown to be minimal under general assumptions.
---
paper_title: Rollback recovery in distributed systems using loosely synchronized clocks

paper_content:

A rollback recovery scheme for distributed systems is proposed. The state-save synchronization among processes is implemented by bounding clock drifts such that no state-save synchronization messages are required. Since the clocks are only loosely synchronized, the synchronization overhead can be negligible in many applications. An interprocess communication protocol which encodes state-save progress information within message frames is introduced to checkpoint consistent system states. A rollback recovery algorithm that will force a minimum number of nodes to roll back after failures is developed. >
---
paper_title: An efficient protocol for checkpointing recovery in distributed systems

paper_content:

The authors present an efficient synchronized checkpointing protocol that exploits the dependency relation between processes in distributed systems. In this protocol, a process takes a checkpoint when it knows that all processes on which it computationally depends took their checkpoints, hence the process need not always wait for the decision made by the checkpointing coordinator as in the conventional synchronized protocols. As a result, the checkpointing coordination time is substantially reduced and the possibility of total abort of the checkpointing coordination is reduced. >
---
paper_title: ON DISTRIBUTED SNAPSHOTS

paper_content:

We develop an efficient snapshot algorithm that needs no control messages and does not require channels to be first-in-first-out. We also show that several stable properties (e.g., termination, deadlock) can be detected with uncoordinated distributed snapshots. For such properties, our algorithm can be further simplified.
---
paper_title: Concurrent robust checkpointing and recovery in distributed systems

paper_content:

A checkpoint/rollback algorithm is presented for multiple processes in a distributed system that uses message passing for communication. Each process in the system can initiate the algorithm autonomously. If only one instance of the algorithm is being executed, the algorithm will force the minimal number of additional processes other than the initiator to make checkpoints (or roll back). The contributions of this research are as follows: (1) the concurrent execution of the algorithm for different global checkpointing instances and rollback instances initiated by several processes is allowed. Deadlocks or livelocks among different global checkpointing instances and rollback instances will not occur; (2) the algorithm is resilient to multiple process failures, and handles network partitioning in a pessimistic way, and (3) the algorithm does not require that messages be received in the order in which they are sent. >
---
paper_title: Rollback and Recovery Strategies for Computer Programs

paper_content:

Reliability is an important aspect of any system. On-line diagnosis, parity check coding, triple modular redundancy, and other methods have been used to improve the reliability of computing systems. In this paper another aspect of reliable computing systems is explored. The problem is that of recovering error-free information when an error is detected at some stage in the processing of a program. If an error or fault is detected while a program is being processed and if it cannot be corrected immediately, it may be necessary to run the entire program again. The time spent in rerunning the program may be substantial and in some real time applications critical. Recovery time can be reduced by saving states of the program (all the information stored in registers, primary and secondary storage, etc.) at intervals, as the processing continues. If an error is detected the program is restarted from its most recently saved state. However, a price is paid in saving a state in the form of time spent storing all the relevant information in secondary storage. Hence it is expensive to save the state of the program too often. Not saving any state of the program may cause an unacceptably large recovery time. The problem that we solve is the following. Determine the optimum points at which the state of the program should be stored to recover after any malfunction.
---
paper_title: Global checkpointing for distributed programs

paper_content:

A novel algorithm for checkpointing and rollback recovery in distributed systems is presented. Processes belonging to the same program must take periodically a nonblocking coordinated global checkpoint, but only a minimum overhead is imposed during normal computation. Messages can be delivered out of order, and the processes are not required to be deterministic. The nonblocking structure is an important characteristic for avoiding laying a heavy burden on the application programs. The method also 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. A possible way to evaluate the error detection latency, which enables one to assess the damage made and avoid the propagation of errors, is presented. >
---
paper_title: Distributed snapshots: determining global states of distributed systems

paper_content:

This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.
---
paper_title: Cache coherence protocols: evaluation using a multiprocessor simulation model

paper_content:

Using simulation, we examine the efficiency of several distributed, hardware-based solutions to the cache coherence problem in shared-bus multiprocessors. For each of the approaches, the associated protocol is outlined. The simulation model is described, and results from that model are presented. The magnitude of the potential performance difference between the various approaches indicates that the choice of coherence solution is very important in the design of an efficient shared-bus multiprocessor, since it may limit the number of processors in the system.
---
paper_title: Cache-aided rollback error recovery (CARER) algorithm for shared-memory multiprocessor systems

paper_content:

Three cache-aided error-recovery algorithms for use in shared-memory multiprocessor systems are presented. They rely on hardware and specially designed cache memory for all their soft error management operations and can be easily incorporated into existing cache-coherence protocols. An example illustrating their use in a multiprocessor system employing Dragon as its cache-coherence protocol is given, and the results of a tradeoff analysis are presented. >
---
paper_title: The Performance of Cache-Based Error Recovery in Multiprocessors

paper_content:

Several variations of cache-based checkpointing for rollback error recovery from transient errors in shared-memory multiprocessors have been recently developed. By modifying the cache replacement policy, these techniques use the inherent redundancy in the memory hierarchy to periodically checkpoint the computation state. Three schemes, different in the manner in which they avoid rollback propagation, are evaluated in this paper. By simulation with address traces from parallel applications running on an Encore Multimax shared-memory multiprocessor, we evaluate the performance effect of integrating the recovery schemes in the cache coherence protocol. Our results indicate that the cache-based schemes can provide checkpointing capability with low performance overhead, but with uncontrollable high variability in the checkpoint interval. >
---
paper_title: Fast recovery in distributed shared virtual memory systems

paper_content:

The problem of system failure and recovery of distributed shared virtual memory (DSVM) is studied. Most DSVM systems use the notion of tokens to indicate a site's access rights on the data pages it caches, and a locating scheme to get to the most up-to-date version of a data page. The problem is to recovery this token directory after a site has failed. The authors' solution is to treat the token directory at each site as a fragment of a global token database and the page migration activities as token transactions that update this distributed database. By the use of the unilateral commit protocol for token transactions, fast recovery of the token state at minimal run-time overhead of token transaction execution is achieved. >
---
paper_title: Dynamic snooping in a fault-tolerant distributed shared memory

paper_content:

Distributed shared memory (DSM) allows multicomputer systems with no physically shared memory to be programmed using a shared memory paradigm. However, as the number of nodes in a system increases the probability of a failure that can corrupt the DSM increases. This paper presents a fault-tolerant DSM (FTDSM) algorithm that can tolerate single node failures. Each page in the DSM is assigned a snooper that keeps a backup copy of the page and can take over if the page owner fails. The snooper is dynamic because the responsibility for snooping a page can migrate front node to node. The FTDSM presented is an improvement over other FTDSMs because it is scalable, is based on the efficient dynamic distributed manager (DDM) DSM algorithm, does not require the repair of a failed processor to access the DSM, and does not query all nodes to rebuild the state of the DSM. It is shown that any single node failure can be tolerated because either the owner or the snooper of a page can always be found. >
---
paper_title: CATCH-compiler-assisted techniques for checkpointing

paper_content:

A compiler-based approach to generating efficient checkpoints for process recovery is described. The presented approach to checkpointing is programmer, operating system, and hardware transparent. Compile-time information is exploited to maintain the desired checkpoint interval and to reduce the size of checkpoints. Compiler-generated sparse potential checkpoint code is used to maintain the desired checkpoint interval. Adaptive checkpointing has been developed to reduce the size of checkpoints by exploiting potentially large variations in memory usage. A training technique is used in selecting the low-cost, high-coverage potential checkpoints. Since the potential checkpoint selection problem is NP-complete, a heuristic algorithm has been developed to obtain a quick suboptimal solution. These compiler-assisted checkpointing techniques have been implemented in a modified version of the GNU C (GCC) compiler version of 1.34. Experiments utilizing the CATCH GCC compiler on SUN workstations are described.<<ETX>>
---
paper_title: A low-overhead recovery technique using quasi-synchronous checkpointing

paper_content:

In this paper, we propose a quasi-synchronous checkpointing algorithm and a low-overhead recovery algorithm based on it. The checkpointing algorithm preserves process autonomy by allowing them to take checkpoints asynchronously and uses communication-induced checkpoint coordination for the progression of the recovery line which helps bound rollback propagation during a recovery. Thus, it has the easiness and low overhead of asynchronous checkpointing and the recovery time advantages of synchronous checkpointing. There is no extra message overhead involved during checkpointing and the additional checkpointing overhead is nominal. The algorithm ensures the existence of a recovery line consistent with the latest checkpoint of any process all the time. The recovery algorithm exploits this feature to restore the system to a state consistent with the latest checkpoint of a failed process. The recovery algorithm has no domino effect and a failed process needs only to rollback to its latest checkpoint and request the other processes to roll back to a consistent checkpoint. To avoid domino effect, it uses selective pessimistic message logging at the receiver end. The recovery is asynchronous for single process failure. Neither the recovery algorithm nor the checkpointing algorithm requires the channels to be FIFO. We do not use vector timestamps for determining dependency between checkpoints since vector timestamps generally result in high message overhead during failure-free operation.
---
paper_title: Rollback and Recovery Strategies for Computer Programs

paper_content:

Reliability is an important aspect of any system. On-line diagnosis, parity check coding, triple modular redundancy, and other methods have been used to improve the reliability of computing systems. In this paper another aspect of reliable computing systems is explored. The problem is that of recovering error-free information when an error is detected at some stage in the processing of a program. If an error or fault is detected while a program is being processed and if it cannot be corrected immediately, it may be necessary to run the entire program again. The time spent in rerunning the program may be substantial and in some real time applications critical. Recovery time can be reduced by saving states of the program (all the information stored in registers, primary and secondary storage, etc.) at intervals, as the processing continues. If an error is detected the program is restarted from its most recently saved state. However, a price is paid in saving a state in the form of time spent storing all the relevant information in secondary storage. Hence it is expensive to save the state of the program too often. Not saving any state of the program may cause an unacceptably large recovery time. The problem that we solve is the following. Determine the optimum points at which the state of the program should be stored to recover after any malfunction.
---
paper_title: A low-overhead recovery technique using quasi-synchronous checkpointing

paper_content:

In this paper, we propose a quasi-synchronous checkpointing algorithm and a low-overhead recovery algorithm based on it. The checkpointing algorithm preserves process autonomy by allowing them to take checkpoints asynchronously and uses communication-induced checkpoint coordination for the progression of the recovery line which helps bound rollback propagation during a recovery. Thus, it has the easiness and low overhead of asynchronous checkpointing and the recovery time advantages of synchronous checkpointing. There is no extra message overhead involved during checkpointing and the additional checkpointing overhead is nominal. The algorithm ensures the existence of a recovery line consistent with the latest checkpoint of any process all the time. The recovery algorithm exploits this feature to restore the system to a state consistent with the latest checkpoint of a failed process. The recovery algorithm has no domino effect and a failed process needs only to rollback to its latest checkpoint and request the other processes to roll back to a consistent checkpoint. To avoid domino effect, it uses selective pessimistic message logging at the receiver end. The recovery is asynchronous for single process failure. Neither the recovery algorithm nor the checkpointing algorithm requires the channels to be FIFO. We do not use vector timestamps for determining dependency between checkpoints since vector timestamps generally result in high message overhead during failure-free operation.
---
paper_title: On the use and implementation of message logging

paper_content:

We present a number of experiments showing that for compute-intensive applications executing in parallel on clusters of workstations, message logging has higher failure-free overhead than coordinated checkpointing. Message logging protocols, however, result in much shorter output latency than coordinated checkpointing. Therefore, message logging should be used for applications involving substantial interactions with the outside world, while coordinated checkpointing should be used otherwise. We also present an unorthodox message logging design that uses coordinated checkpointing with message logging, departing from the conventional approaches that use independent checkpointing. This combination of message logging and coordinated checkpointing offers several advantages, including improved failure-free performance, bounded recovery time, simplified garbage collection, and reduced complexity. Meanwhile, the new protocols retain the advantages of the conventional message logging protocols with respect to output commit. Finally, we discuss three "lessons learned" from an implementation of various message logging protocols. >
---
paper_title: Experimental evaluation of concurrent checkpointing and rollback-recovery algorithms

paper_content:

The performance of two distributed checkpointing and recovery algorithms, the synchronous checkpointing algorithm (SA) and the independent checkpointing algorithm (ICA), is evaluated. The performance is based on a detailed implementation of algorithms published earlier in the C language. A benchmark that simulates a variety of application requirements and considers variations in the number of processes running on one or more machines, size of processes to be checkpointed, size of control messages, and frequency of message exchanges for normal processing is used to conduct the experiments. Measurements are made for the elapsed time and the CPU time to run a single instance of the checkpoint or rollback. The experiments are repeated for various combinations of concurrent checkpoint and rollback executions. The messages needed for synchronization are computed. It is found that the time that a process spends in processing control messages contributes significantly to the elapsed time in both algorithms. Elapsed times for recovery for both algorithms are found to be comparable when the number of checkpoints is small. >
---
paper_title: The integration of virtual memory management and interprocess communication in Accent

paper_content:

The integration of virtual memory management and interprocess communication in the Accent network operating system kernel is examined. The design and implementation of the Accent memory management system is discussed and its performance, both on a series of message-oriented benchmarks and in normal operation, is analyzed in detail.
---
paper_title: Virtual checkpoints: architecture and performance

paper_content:

Checkpoint and rollback recovery is a technique that allows a system to tolerate a failure by periodically saving the entire state and, if an error is detected, rolling back to the prior checkpoint. A technique that embeds the support for checkpoint and rollback recovery directly into the virtual memory translation hardware is presented. The scheme is general enough to be implemented on various scopes of data such as a portion of an address space, a single address space, or multiple address spaces. The technique can provide a high-performance scheme for implementing checkpoint and rollback recovery. The performance. of the scheme is analyzed using a trace-driven simulation. The overhead is a function of the interval between checkpoints and becomes very small for intervals greater than 10/sup 6/ references. However, the scheme is shown to be feasible for intervals as small as 1000 references under certain conditions. >
---
paper_title: RAID: high-performance, reliable secondary storage

paper_content:

Disk arrays were proposed in the 1980s as a way to use parallelism between multiple disks to improve aggregate I/O performance. Today they appear in the product lines of most major computer manufacturers. This article gives a comprehensive overview of disk arrays and provides a framework in which to organize current and future work. First, the article introduces disk technology and reviews the driving forces that have popularized disk arrays: performance and reliability. It discusses the two architectural techniques used in disk arrays: striping across multiple disks to improve performance and redundancy to improve reliability. Next, the article describes seven disk array architectures, called RAID (Redundant Arrays of Inexpensive Disks) levels 0–6 and compares their performance, cost, and reliability. It goes on to discuss advanced research and implementation topics such as refining the basic RAID levels to improve performance and designing algorithms to maintain data consistency. Last, the article describes six disk array prototypes of products and discusses future opportunities for research, with an annotated bibliography disk array-related literature.
---
paper_title: CATCH-compiler-assisted techniques for checkpointing

paper_content:

A compiler-based approach to generating efficient checkpoints for process recovery is described. The presented approach to checkpointing is programmer, operating system, and hardware transparent. Compile-time information is exploited to maintain the desired checkpoint interval and to reduce the size of checkpoints. Compiler-generated sparse potential checkpoint code is used to maintain the desired checkpoint interval. Adaptive checkpointing has been developed to reduce the size of checkpoints by exploiting potentially large variations in memory usage. A training technique is used in selecting the low-cost, high-coverage potential checkpoints. Since the potential checkpoint selection problem is NP-complete, a heuristic algorithm has been developed to obtain a quick suboptimal solution. These compiler-assisted checkpointing techniques have been implemented in a modified version of the GNU C (GCC) compiler version of 1.34. Experiments utilizing the CATCH GCC compiler on SUN workstations are described.<<ETX>>
---
paper_title: Efficient algorithms for selection of recovery points in tree task models

paper_content:

Efficient solutions to the problem of optimally selecting recovery points are developed. The solutions are intended for models of computation in which task precedence has a tree structure and a task may fail due to the presence of faults. An algorithm to minimize the expected computation time of the task system under a uniprocessor environment has been developed for the binary tree model. The algorithm has time complexity of O(N/sub 2/), where N is the number of tasks, while previously reported procedures have exponential time requirements. The results are generalized for an arbitrary tree model. >
---
paper_title: A watchdog processor based general rollback technique with multiple retries

paper_content:

A common assumption in the existing rollback techniques is that transients, the cause of most failures, subside very quickly, implying that a single story retry of the program from the previous rollback point is sufficient. The authors discuss a general rollback strategy with n(n≥2) retries which takes into consideration multiple transient failures as well as transients of long duration. Ways of deriving practical values of n for a given program are also discussed. Furthermore, the authors propose the use of a watchdog processor as an error detection tool to initiate recovery action through rollback, since the watchdog processor offers low error latency. They also discuss the merging of the watchdog processor with rollback recovery technique for enhancing the overall system reliability.
---
paper_title: Recovery point selection on a reverse binary tree task model

paper_content:

An analysis is conducted of the complexity of placing recovery points where the computation is modeled as a reverse binary tree task model. The objective is to minimize the expected computation time of a program in the presence of faults. The method can be extended to an arbitrary reverse tree model. For uniprocessor systems, an optimal placement algorithm is proposed. For multiprocessor systems, a procedure for computing their performance is described. Since no closed form solution is available, an alternative measurement is proposed that has a closed form formula. On the basis of this formula, algorithms are devised for solving the recovery point placement problem. The estimated formula can be extended to include communication delays where the algorithm devised still applies. >
---
paper_title: Rollback and Recovery Strategies for Computer Programs

paper_content:

Reliability is an important aspect of any system. On-line diagnosis, parity check coding, triple modular redundancy, and other methods have been used to improve the reliability of computing systems. In this paper another aspect of reliable computing systems is explored. The problem is that of recovering error-free information when an error is detected at some stage in the processing of a program. If an error or fault is detected while a program is being processed and if it cannot be corrected immediately, it may be necessary to run the entire program again. The time spent in rerunning the program may be substantial and in some real time applications critical. Recovery time can be reduced by saving states of the program (all the information stored in registers, primary and secondary storage, etc.) at intervals, as the processing continues. If an error is detected the program is restarted from its most recently saved state. However, a price is paid in saving a state in the form of time spent storing all the relevant information in secondary storage. Hence it is expensive to save the state of the program too often. Not saving any state of the program may cause an unacceptably large recovery time. The problem that we solve is the following. Determine the optimum points at which the state of the program should be stored to recover after any malfunction.
---
paper_title: Distributed snapshots: determining global states of distributed systems

paper_content:

This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.
---

Title: A Survey of Checkpointing Algorithms for Parallel and Distributed Computers

Section 1: Introduction
Description 1: Introduce the basics of checkpointing, define key terms, and explain the necessity of fault tolerance in parallel and distributed systems.

Section 2: Application of checkpointing
Description 2: Discuss how checkpointing is used to recover from failures, debug distributed programs, and migrate processes in multiprocessor systems.

Section 3: Checkpointing in uniprocessor systems
Description 3: Describe the process and methodology of checkpointing in uniprocessor systems, highlighting the simplicity due to total ordering of events.

Section 4: Checkpointing in distributed systems
Description 4: Explain the complexities involved in checkpointing in distributed systems, focusing on the absence of a global clock and the need for concurrent checkpoints.

Section 5: Ordering of events in distributed systems
Description 5: Define key concepts like 'happens before' relation, concurrent events, local checkpoint, global checkpoint, consistent global checkpoint, and rollback recovery.

Section 6: Aspects of checkpointing
Description 6: Discuss various aspects to consider for checkpointing, including frequency, contents, and methods of checkpointing.

Section 7: Overheads of a checkpointing algorithm
Description 7: Define the different types of overheads involved in checkpointing, such as coordination overhead and context-saving overhead.

Section 8: Organisation of the paper
Description 8: Provide an overview of the structure of the paper, summarising what each subsequent section will cover.

Section 9: Checkpointing algorithms for message-passing systems
Description 9: Detail checkpointing algorithms tailored for message-passing systems, specifically focusing on Chandy and Lamport's algorithm and its modifications.

Section 10: Checkpointing algorithms for shared-memory systems
Description 10: Discuss checkpointing algorithms designed for shared-memory systems and the role of cache coherence protocols.

Section 11: Checkpointing algorithms for distributed shared-memory systems
Description 11: Explain checkpointing in distributed shared-memory systems and the need to save contexts in stable storage to withstand node failures.

Section 12: Classification of checkpointing algorithms
Description 12: Present a classification tree and list the desirable features for checkpointing algorithms.

Section 13: Future direction of research in checkpointing
Description 13: Summarise shared and distributed shared-memory checkpointing algorithms' current status, discuss message-passing algorithms, propose ways to minimise context-saving overhead, and explore the potential of static approaches.

Section 14: Conclusions
Description 14: Conclude with a summary of the literature on checkpointing algorithms, highlighting areas for potential improvement and future research directions.