A Review of Fault Tolerant Checkpointing Protocols for Mobile Computing Systems
---
paper_title: Finding Consistent Global Checkpoints in a Distributed Computation

paper_content:

Consistent global checkpoints have many uses in distributed computations. A central question in applications that use consistent global checkpoints is to determine whether a consistent global checkpoint that includes a given set of local checkpoints can exist. Netzer and Xu (1995) presented the necessary and sufficient conditions under which such a consistent global checkpoint can exist, but they did not explore what checkpoints could be constructed. In this paper, we prove exactly which local checkpoints can be used for constructing such consistent global checkpoints. We illustrate the use of our results with a simple and elegant algorithm to enumerate all such consistent global checkpoints.
---
paper_title: Independent checkpointing and concurrent rollback for recovery in distributed systems-an optimistic approach

paper_content:

A checkpoint algorithm is presented that benefits from the research in concurrency control, commit, and site recovery algorithms in transaction processing. In the authors' approach a number of checkpointing processes, a number of rollback processes, and computations on operational processes can proceed concurrently while tolerating the failure of an arbitrary number of processes. Each process takes checkpoints independently. During recovery after a failure, a process invokes a two-phase rollback algorithm. It collects information about relevant message exchanges in the system in the first phase and uses it in the second phase to determine both the set of processes that must roll back and the set of checkpoints up to which rollback must occur. Concurrent rollbacks are completed in the order of the priorities of the recovering processes. The proposed solution is optimistic in the sense that it does well if failures are infrequent by minimizing overhead during normal processing. >
---
paper_title: Checkpointing and its applications

paper_content:

The paper describes our experience with the implementation and applications of the Unix checkpointing library libckp, and identifies two concepts that have proven to be the key to making checkpointing a powerful tool. First, including all persistent states, i.e., user files, as part of the process state that can be checkpointed and recovered provides a truly transparent and consistent rollback. Second, excluding part of the persistent state from the process state allows user programs to process future inputs from a desirable state, which leads to interesting new applications of checkpointing. We use real-life examples to demonstrate the use of libckp for bypassing premature software exits, for fast initialization and for memory rejuvenation. >
---
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: State Restoration in Systems of Communicating Processes

paper_content:

In systems of asynchronous processes using messagelists with SEND–RECEIVE primitives for interprocess communication recovery primitives are defined to perform state restoration: MARK saves a particular point in the execution of the program; RESTORE resets the system state to an earlier point (saved by MARK); and PURGE discards redundant information when it is no longer needed for possible state restoration.
---
paper_title: A survey of rollback-recovery protocols in message-passing systems

paper_content:

This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols into checkpoint-based and log-based. Checkpoint-based protocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced. Log-based protocols combine checkpointing with logging of nondeterministic events, encoded in tuples called determinants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback-recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
---
paper_title: Independent checkpointing and concurrent rollback for recovery in distributed systems-an optimistic approach

paper_content:

A checkpoint algorithm is presented that benefits from the research in concurrency control, commit, and site recovery algorithms in transaction processing. In the authors' approach a number of checkpointing processes, a number of rollback processes, and computations on operational processes can proceed concurrently while tolerating the failure of an arbitrary number of processes. Each process takes checkpoints independently. During recovery after a failure, a process invokes a two-phase rollback algorithm. It collects information about relevant message exchanges in the system in the first phase and uses it in the second phase to determine both the set of processes that must roll back and the set of checkpoints up to which rollback must occur. Concurrent rollbacks are completed in the order of the priorities of the recovering processes. The proposed solution is optimistic in the sense that it does well if failures are infrequent by minimizing overhead during normal processing. >
---
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: State Restoration in Systems of Communicating Processes

paper_content:

In systems of asynchronous processes using messagelists with SEND–RECEIVE primitives for interprocess communication recovery primitives are defined to perform state restoration: MARK saves a particular point in the execution of the program; RESTORE resets the system state to an earlier point (saved by MARK); and PURGE discards redundant information when it is no longer needed for possible state restoration.
---
paper_title: A survey of rollback-recovery protocols in message-passing systems

paper_content:

This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols into checkpoint-based and log-based. Checkpoint-based protocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced. Log-based protocols combine checkpointing with logging of nondeterministic events, encoded in tuples called determinants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback-recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
---
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: The Performance of Consistent Checkpointing

paper_content:

Consistent checkpointing provides transparent fault tolerance for long-running distributed applications. Performance measurements of an implementation of consistent checkpointing are described. The measurements show that consistent checkpointing performs remarkably well. Eight computation-intensive distributed applications were executed on a network of 16 diskless Sun-3/60 workstations, and the performance without checkpointing was compared to the performance with consistent checkpoints taken at two-minute intervals. For six of the eight applications, the running time increased by less than 1% as a result of the checkpointing. The highest overhead measured was 5.8%. Incremental checkpointing and copy-on write checkpointing were the most effective techniques in lowering the running time overhead. It is argued that these measurements show that consistent checkpointing is an efficient way to provide fault tolerance for long-running distributed applications. >
---
paper_title: Communication-Induced Determination of Consistent Snapshots

paper_content:

A classical way to determine consistent snapshots consists in using Chandy-Lamport's algorithm. This algorithm relies on specific control messages that allow processes to synchronize local checkpoint determination and message recording in order for the resulting snapshot to be consistent. This paper investigates a communication-induced approach to determine consistent snapshots. In such an approach, control information is carried out by application messages. Two abstract necessary and sufficient conditions are stated: one associated with global checkpoint consistency, the other associated with message recording. A general protocol is derived from these abstract conditions. Actually, this general protocol can be instantiated in distinct ways, giving rise to a family of communication-induced snapshot protocols. This general protocol shows there is an intrinsic trade-off between the number of forced checkpoints and the number of recorded messages. Finally, a particular instantiation of the general protocol is provided.
---
paper_title: Quasi-Synchronous Checkpointing: Models, Characterization, and Classification

paper_content:

Checkpointing algorithms are classified as synchronous and asynchronous in the literature. In synchronous checkpointing, processes synchronize their checkpointing activities so that a globally consistent set of checkpoints is always maintained in the system. Synchronizing checkpointing activity involves message overhead and process execution may have to be suspended during the checkpointing coordination, resulting in performance degradation. In asynchronous checkpointing, processes take checkpoints without any coordination with others. Asynchronous checkpointing provides maximum autonomy for processes to take checkpoints; however, some of the checkpoints taken may not lie on any consistent global checkpoint, thus making the checkpointing efforts useless. Asynchronous checkpointing algorithms in the literature can reduce the number of useless checkpoints by making processes take communication induced checkpoints besides asynchronous checkpoints. We call such algorithms quasi-synchronous. In this paper, we present a theoretical framework for characterizing and classifying such algorithms. The theory not only helps to classify and characterize the quasi-synchronous checkpointing algorithms, but also helps to analyze the properties and limitations of the algorithms belonging to each class. It also provides guidelines for designing and evaluating such algorithms.
---
paper_title: A survey of rollback-recovery protocols in message-passing systems

paper_content:

This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols into checkpoint-based and log-based. Checkpoint-based protocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced. Log-based protocols combine checkpointing with logging of nondeterministic events, encoded in tuples called determinants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback-recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
---
paper_title: A communication-induced checkpointing protocol that ensures rollback-dependency trackability

paper_content:

Considering an application in which processes take local checkpoints independently (called basic checkpoints), this paper develops a protocol that forces them to take some additional local checkpoints (called forced checkpoints) in order that the resulting checkpoint and communication pattern satisfies the Rollback Dependency Trackability (RDT) property. This property states that all dependencies between local checkpoints are on-line trackable by using a transitive dependency vector. Compared to other protocols ensuring the RDT property, the proposed protocol is less conservative in the sense that it takes less additional local checkpoints. It attains this goal by a subtle tracking of causal dependencies on already taken checkpoints; this tracking is then used to prevent the occurrence of hidden dependencies. As indicated by simulation study, the proposed protocol compares favorably with other protocols; moreover it additionally associates on-the-fly with each local checkpoint C the minimum global checkpoint to which C belongs.
---
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: Message logging in mobile computing

paper_content:

Dependable mobile computing is enhanced by independent recovery, low power consumption and no dependence on stable storage at the mobile host. Existing recovery protocols proposed for mobile environments typically create consistent global checkpoints that do not guarantee independent recovery and low power consumption. This paper demonstrates the advantages of message logging by describing a receiver based logging protocol. Cheap pointing is utilized to limit log size and recovery latency. We compare the performance of our approach with that of existing mobile checkpointing and recovery algorithms in terms of failure free overhead and recovery time. We also describe a stable storage management scheme for mobile support stations. Garbage collection is achieved without direct participation of mobile hosts.
---
paper_title: Manetho: Transparent rollback-recovery with low overhead, limited rollback and fast output commit

paper_content:

Manetho is a new transparent rollback-recovery protocol for long-running distributed computations. It uses a novel combination of antecedence graph maintenance, uncoordinated checkpointing, and sender-based message logging. Manetho simultaneously achieves the advantages of pessimistic message logging, namely limited rollback and, fast output commit, and the advantage of optimistic message logging, namely low failure-free overhead. These advantages come at the expense of a complex recovery scheme. >
---
paper_title: Efficient distributed recovery using message logging

paper_content:

Absfrucf: Various distributed algorithms am presented, that allow nodes in a distributed system to recover from crash failures efficiently. The algorithms are independent of the application programs running on the nodes. The algorithms log messages and checkpoint states of the processes to stable storage at each node. Both logging of messages and checkpointing of process states can be done asynchronously with the execution of the application. Upon restarting after a failure, a node initiates a procedure in which the nodes use the logs and checkpoints on stable storage to roll back to earlier local states, such that the resulting global state is maximal and consistent. The first algorithm requires adding extra information of size O(n) to each application message (where n is the number of nodes); for each failure, O(n2) messages are exchanged, but no node rolls back more than once. The second algorithm only requires extra information of size O(1) on each application message, but requires O(n3) messages per failure. Both the above algorithms require that each process should be able to send messages to each of the other processes. We also present algorithms for recovery on networks, in which each process only communicates with its neighbors. Finally, we show how to decompose large networks into smaller networks so that each of the smaller network can use a different recovery procedure.
---
paper_title: Message Logging: Pessimistic, Optimistic, Causal, and Optimal

paper_content:

Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All message-logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property "no orphan processes". From this specification, we describe how different existing classes of message-logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message-logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f (1/spl les/f/spl les/n).
---
paper_title: A survey of rollback-recovery protocols in message-passing systems

paper_content:

This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols into checkpoint-based and log-based. Checkpoint-based protocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced. Log-based protocols combine checkpointing with logging of nondeterministic events, encoded in tuples called determinants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback-recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
---
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: Optimistic crash recovery without rolling back nonfaulty processors

paper_content:

Abstract The problem of recovering from transient processor failures in distributed computing systems using optimistic message logging is considered, and two crash recovery algorithms are presented. Both algorithms have three advantages: 1. (1) no nonfaulty processor is forced to roll back 2. (2) output messages may be committed immediately, and 3. (3) a nonfaulty processor is not disrupted if none of its neighbors is faulty. The first algorithm uses acknowledgments, permits at most two neighboring processors to fail at the same time, and does not block the receiver or the sender of each message. The second algorithm copes with the simultaneous failure of any number of nodes, but it requires that the sender id of each message (not its content) be logged to stable storage before the message is processed. Though the second algorithm blocks the receiver, the blocking time can be substantially reduced. In both cases, the state of a faulty processor immediately before its failure is recreated. Thus, after either of the two crash recovery algorithms is run, the distributed system restarts from a consistent state.
---
paper_title: A message system supporting fault tolerance

paper_content:

A simple and general design uses message-based communication to provide software tolerance of single-point hardware failures. By delivering all interprocess messages to inactive backups for both the sender and the destination, both backups are kept in a state in which they can take over for their primaries. An implementation for the Auragen 4000 series of M68000-based systems is described. The operating system, Auros TM , is a distributed version of UNIX*. Major goals have been transparency of fault tolerance and efficient execution in the absence of failure.
---
paper_title: Understanding The Message Logging Paradigm For Masking Process Crashes

paper_content:

Message logging is a popular technique for building systems that can tolerate process crashes and transient channel failures. The technique, which was first developed in the mid-80s, is popular because message logging protocols are relatively simple and require process replication only when a process fails. Surprisingly, however, very little attention has been given to the formal specification of the consistency property that these protocols implement in order to be able to recover failed processes to a consistent state. ::: This dissertation presents the first such formal specification. From this specification, the two major classes of message logging protocols, namely optimistic and pessimistic, are characterized. A third and new class of message logging protocols, called causal, is introduced. A notion of optimality, based on three important performance metrics, is proposed, and it is shown that optimal implementations of causal message logging protocols exist. In particular, it is shown that causal message logging protocols combine the positive aspects of optimistic and pessimistic message logging. ::: A subclass of causal message logging protocols, called family-based logging, is developed. Family-based logging protocols are optimal and have the additional attractive characteristic that the smaller the maximum number of concurrent failures, the lower their overhead. Furthermore, several compression techniques can be used to reduce this overhead. Finally, it is shown that family-based logging protocols can be implemented in order to take advantage of the different patterns of communication that systems exhibit.
---
paper_title: Error detection in large-scale parallel programs with long runtimes

paper_content:

Error detection is an important activity of program development, which is applied to detect incorrect computations or runtime failures of software. The costs of debugging are strongly related to the complexity and the scale of the investigated programs. Both characteristics are especially cumbersome for large-scale parallel programs with long runtimes, which are quite common in computational science and engineering (CSE) applications. A solution is offered by a combination of techniques using the event graph model as a representation of parallel program behaviour. With process isolation, a subset of the original number of processes can be investigated, while the absent processes are simulated by the debugging system. With checkpointing, an arbitrary temporal section of a program's runtime can be extracted for exhaustive analysis without the need to restart the program from the beginning. Additional benefits of the event graph are support of equivalent execution of nondeterministic programs, as well as a comprehensible visualisation as a space-time diagram.
---
paper_title: Distributed snapshots for mobile computing systems

paper_content:

Accomplishing the distributed snapshots problem in mobile systems is an important issue as well as in distributed systems. This work presents a distributed snapshots protocol for mobile computing systems. In addition, this protocol can be used for achieving an efficient checkpointing protocol in the mobile environment. Specifically, it is a robust adaptation of the classical distributed snapshots protocol, where the mobile hosts can still roam among the different cells within the mobile system. The main benefit of this work is to provide distributed snapshots for a mobile system without adding any restriction to the system, such as FIFO ordering among the application messages as required for a traditional distributed system.
---
paper_title: Low-Cost Checkpointing and Failure Recovery in Mobile Computing Systems

paper_content:

A mobile computing system consists of mobile and stationary nodes, connected to each other by a communication network. The presence of mobile nodes in the system places constraints on the permissible energy consumption and available communication bandwidth. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system (checkpoint) is required. Locating mobile nodes contributes to the checkpointing and recovery costs. Synchronous snapshot collection algorithms, designed for static networks, either force every node in the system to take a new local snapshot, or block the underlying computation during snapshot collection. Hence, they are not suitable for mobile computing systems. If nodes take their local checkpoints independently in an uncoordinated manner, each node may have to store multiple local checkpoints in stable storage. This is not suitable for mobile nodes as they have small memory. This paper presents a synchronous snapshot collection algorithm for mobile systems that neither forces every node to take a local snapshot, nor blocks the underlying computation during snapshot collection. If a node initiates snapshot collection, local snapshots of only those nodes that have directly or transitively affected the initiator since their last snapshots need to be taken. We prove that the global snapshot collection terminates within a finite time of its invocation and the collected global snapshot is consistent. We also propose a minimal rollback/recovery algorithm in which the computation at a node is rolled back only if it depends on operations that have been undone due to the failure of node(s). Both the algorithms have low communication and storage overheads and meet the low energy consumption and low bandwidth constraints of mobile computing systems.
---
paper_title: A distributed consistent global checkpoint algorithm for distributed mobile systems

paper_content:

A distributed coordinated checkpointing algorithm for distributed mobile systems is presented. A consistent global checkpoint is a set of states in which no message is recorded as received in one process and as not yet sent in another process. It is used for rollback when process failure occurs. A consistent global checkpoint must be obtained for any checkpoint initiation by any process. This paper shows a checkpoint algorithm in which the amount of information piggybacked on program messages does not depend on the number of mobile processes. The number of checkpoints is minimized under two assumptions: (1) one consistent global checkpoint is taken for concurrent checkpoint initiations and (2) a checkpoint is initiated at each handoff by mobile processes. This algorithm is thus optimal among the generalizations of Chandy and Lamport's distributed snapshot algorithm under the latter assumption.
---
paper_title: Mutable checkpoints: a new checkpointing approach for mobile computing systems

paper_content:

Mobile computing raises many new issues such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. Coordinated checkpointing is an attractive approach for transparently adding fault tolerance to distributed applications since it avoids domino effects and minimizes the stable storage requirement. However, it suffers from high overhead associated with the checkpointing process in mobile computing systems. Two approaches have been used to reduce the overhead: First is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process nonblocking. These two approaches were orthogonal previously until the Prakash-Singhal algorithm combined them. However, we found that this algorithm may result in an inconsistency in some situations and we proved that there does not exist a nonblocking algorithm which forces only a minimum number of processes to take their checkpoints. In this paper; we introduce the concept of "mutable checkpoint," which is neither a tentative checkpoint nor a permanent checkpoint, to design efficient checkpointing algorithms for mobile computing systems. Mutable checkpoints can be saved anywhere, e.g., the main memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring large amounts of data to the stable storage at MSSs over the wireless network. We present techniques to minimize the number of mutable checkpoints. Simulation results show that the overhead of taking mutable checkpoints is negligible. Based on mutable checkpoints, our nonblocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on the stable storage.
---
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: Low-Cost Checkpointing and Failure Recovery in Mobile Computing Systems

paper_content:

A mobile computing system consists of mobile and stationary nodes, connected to each other by a communication network. The presence of mobile nodes in the system places constraints on the permissible energy consumption and available communication bandwidth. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system (checkpoint) is required. Locating mobile nodes contributes to the checkpointing and recovery costs. Synchronous snapshot collection algorithms, designed for static networks, either force every node in the system to take a new local snapshot, or block the underlying computation during snapshot collection. Hence, they are not suitable for mobile computing systems. If nodes take their local checkpoints independently in an uncoordinated manner, each node may have to store multiple local checkpoints in stable storage. This is not suitable for mobile nodes as they have small memory. This paper presents a synchronous snapshot collection algorithm for mobile systems that neither forces every node to take a local snapshot, nor blocks the underlying computation during snapshot collection. If a node initiates snapshot collection, local snapshots of only those nodes that have directly or transitively affected the initiator since their last snapshots need to be taken. We prove that the global snapshot collection terminates within a finite time of its invocation and the collected global snapshot is consistent. We also propose a minimal rollback/recovery algorithm in which the computation at a node is rolled back only if it depends on operations that have been undone due to the failure of node(s). Both the algorithms have low communication and storage overheads and meet the low energy consumption and low bandwidth constraints of mobile computing systems.
---
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: Low overhead optimal checkpointing for mobile distributed systems

paper_content:

A checkpoint algorithm for a mobile distributed computing system (MDCS) needs to handle many new issues like: mobility, low bandwidth of wireless channels, lack of stable storage on mobile nodes, disconnections, limited battery power and high failure rate of mobile nodes. These issues make traditional checkpointing techniques unsuitable for mobile distributed systems. Coordinated checkpointing may be useful to checkpoint MDCS if it is nonblocking and require minimum number of processes to checkpoint. Cao and Singhal [G. Cao et al., (2001)] achieved both by introducing the concept of mutable checkpoints. Many of these mutable checkpoints may be useless. We propose a nonblocking minimum process coordinated checkpointing protocol that not only minimizes useless checkpoints but also minimizes overall bandwidth required over wireless channels.
---
paper_title: A non-intrusive minimum process synchronous checkpointing protocol for mobile distributed systems

paper_content:

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channels, high mobility and limited battery life. These issues make traditional checkpointing algorithms unsuitable for checkpointing mobile distributed systems. Minimum process coordinated checkpointing is a good approach to introducing fault tolerance in a distributed system transparently. This approach is domino-free and requires at most two checkpoints of each process on stable storage, and forces only interacting processes to checkpoint. Sometimes, it also requires piggybacking of information onto normal messages, blocking of the underlying computation or taking some useless checkpoints. In this paper, we propose a non-intrusive minimum process synchronous checkpointing protocol for mobile distributed systems, where only the minimum number of tentative checkpoints is taken. We also optimize the number of useless forced (mutable) checkpoints and message overheads as compared to Cao et al. (2001).
---
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: Recovery in Distributed Systems Using Optimistic Message Logging and Checkpointing

paper_content:

Message logging and checkpointing can provide fault tolerance in distributed systems in which all process communication is through messages. This paper presents a general model for reasoning about recovery in these systems. Using this model, we prove that the set of recoverable system states that have occurred during any single execution of the system forms a lattice, and that therefore, there is always a unique maximum recoverable system state, which never decreases. Based on this model, we present an algorithm for determining this maximum recoverable state and prove its correctness. Our algorithm utilizes all logged messages and checkpoints, and thus always finds the maximum recoverable state possible. Previous recovery methods using optimistic message logging and checkpointing have not considered the existing checkpoints, and thus may not find this maximum state. Furthermore, by utilizing the checkpoints, some messages received by a process before it was checkpointed may not need to be logged. Using our algorithm also adds less communication overhead to the system than do previous methods. Our model and algorithm can be used with any message logging protocol, whether pessimistic or optimistic, but their full generality is only required with
---
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: 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: Recoverable mobile environment: design and trade-off analysis

paper_content:

The mobile wireless environment poses challenging problems in designing fault-tolerant systems because of the dynamics of mobility, and limited bandwidth available on wireless links. Traditional fault-tolerance schemes, therefore, cannot be directly applied to these systems. Mobile systems are often subject to environmental conditions which can cause loss of communications or data. Because of the consumer orientation of most mobile systems, run-time faults must be corrected with minimal (if any) intervention from the user. The fault-tolerance capability must, therefore, be transparent to the user. The paper presents recovery schemes for the failure of a mobile host. It portrays the limitations of the mobile wireless environment, and their impact on recovery protocols. The adaptation of well-known recovery schemes are presented which suit the mobile environment. The performance of these schemes has been analyzed to determine those environments where a particular recovery scheme is best suited. The performance of the recovery schemes primarily depends on: the wireless bandwidth; the communication-mobility ratio of the user; and the failure rate of the mobile host.
---
paper_title: Independent checkpointing and concurrent rollback for recovery in distributed systems-an optimistic approach

paper_content:

A checkpoint algorithm is presented that benefits from the research in concurrency control, commit, and site recovery algorithms in transaction processing. In the authors' approach a number of checkpointing processes, a number of rollback processes, and computations on operational processes can proceed concurrently while tolerating the failure of an arbitrary number of processes. Each process takes checkpoints independently. During recovery after a failure, a process invokes a two-phase rollback algorithm. It collects information about relevant message exchanges in the system in the first phase and uses it in the second phase to determine both the set of processes that must roll back and the set of checkpoints up to which rollback must occur. Concurrent rollbacks are completed in the order of the priorities of the recovering processes. The proposed solution is optimistic in the sense that it does well if failures are infrequent by minimizing overhead during normal processing. >
---
paper_title: Checkpoint-recovery protocol for reliable mobile systems

paper_content:

Information systems consist of mobile stations and fixed stations. Mission critical applications are required to be executed fault-tolerantly in these systems. However, mobile stations support neither enough volume of storage and processing power nor enough capacity of battery to do reliable, long-term communications. Moreover, wireless channels are less reliable. Hence, the channels with the mobile stations are often disconnected. Therefore, it is difficult for multiple mobile stations to synchronously take checkpoints since the communication channels with the mobile stations may be disconnected even during taking the checkpoints. In this paper, we propose a novel hybrid checkpointing protocol where the mobile stations take asynchronously and the fixed ones take synchronously checkpoints. Reliable information systems including mobile stations can be realized by the hybrid checkpointing protocol.
---
paper_title: Adaptive Checkpointing with Storage Management for Mobile Environments

paper_content:

~~ The limited stable storage available in mobile-computing environments can make tradi- tional checkpointing and message logging umuitable. Since storage on a mobile liost is not considered stable, most pro- tocols designed for these environments save the checkpoints on base stations. Previous approaches have assumed that the base station always has sufficient disk space for storing checkpoints. If there is not enongh storage available, checkpoints might need to be aborted. This paper describes an adaptive protocol that manages stor- age for base stations. The protocol integrates leasing stor- age management with a time-based coordinated checkpointing mechanism. The leasing enables storage managers to control disk-space effectively. Lcasing prevcnts hanged proccsses horn indefinitely retaining storage and, in addition, garbage collec- iion is simple. Time-based checkpointing is integrated with leasing to reduce the number of messages for establishing con- sistent global states. The checkpointing mechanism uses a 3- ievel storage hierarchy to improve checkpointing performance. I'eribKmance was evaluated by both implementation experi- ments and simulations. Thc results show that: . the adaptive protocol reduccs checkpointing ovcrhead, . the leasing mechanism maintains the desired storage assign- ment for base stations.
---
paper_title: Message logging in mobile computing

paper_content:

Dependable mobile computing is enhanced by independent recovery, low power consumption and no dependence on stable storage at the mobile host. Existing recovery protocols proposed for mobile environments typically create consistent global checkpoints that do not guarantee independent recovery and low power consumption. This paper demonstrates the advantages of message logging by describing a receiver based logging protocol. Cheap pointing is utilized to limit log size and recovery latency. We compare the performance of our approach with that of existing mobile checkpointing and recovery algorithms in terms of failure free overhead and recovery time. We also describe a stable storage management scheme for mobile support stations. Garbage collection is achieved without direct participation of mobile hosts.
---
paper_title: Recovery protocol for mobile checkpointing

paper_content:

Information systems consist of multiple mobile stations and fixed stations communicating with each other. Mission critical applications are required to be executed fault tolerantly in these systems. However, mobile stations support neither enough volume of storage and processing power nor enough capacity of battery to do reliable communication for a long period. Moreover, wireless communication channels are less reliable. Hence, the communication channels with mobile stations are often disconnected. Therefore, it is difficult for multiple mobile stations to take checkpoints synchronously since the communication channels with the mobile stations may be disconnected even while taking the checkpoints. We have proposed hybrid checkpointing where checkpoints are taken asynchronously by the mobile stations and synchronously by the fixed stations. In addition, the mobile stations record messages for getting local states consistent with the checkpoints taken by the fixed stations. We propose a method for how the mobile stations record the messages, gather the messages stored in the stable storage distributed in multiple mobile stations, and recompute the messages in a consistent order.
---
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: 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: Quasi-Synchronous Checkpointing: Models, Characterization, and Classification

paper_content:

Checkpointing algorithms are classified as synchronous and asynchronous in the literature. In synchronous checkpointing, processes synchronize their checkpointing activities so that a globally consistent set of checkpoints is always maintained in the system. Synchronizing checkpointing activity involves message overhead and process execution may have to be suspended during the checkpointing coordination, resulting in performance degradation. In asynchronous checkpointing, processes take checkpoints without any coordination with others. Asynchronous checkpointing provides maximum autonomy for processes to take checkpoints; however, some of the checkpoints taken may not lie on any consistent global checkpoint, thus making the checkpointing efforts useless. Asynchronous checkpointing algorithms in the literature can reduce the number of useless checkpoints by making processes take communication induced checkpoints besides asynchronous checkpoints. We call such algorithms quasi-synchronous. In this paper, we present a theoretical framework for characterizing and classifying such algorithms. The theory not only helps to classify and characterize the quasi-synchronous checkpointing algorithms, but also helps to analyze the properties and limitations of the algorithms belonging to each class. It also provides guidelines for designing and evaluating such algorithms.
---
paper_title: On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems

paper_content:

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.
---
paper_title: Checkpointing With Mutable Checkpoints

paper_content:

There are two approaches to reduce the overhead associated with coordinated checkpointing: first is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process non-blocking. In our previous work (IEEE Parallel Distributed Systems 9 (12) (1998) 1213), we proved that there does not exist a nonblocking algorithm which forces only a minimum number of processes to take their checkpoints. In this paper, we present a min-process algorithm which relaxes the non-blocking condition while tries to minimize the blocking time, and a non-blocking algorithm which relaxes the min-process condition while minimizing the number of checkpoints saved on the stable storage. The proposed non-blocking algorithm is based on the concept of "mutable checkpoint", which is neither a tentative checkpoint nor a permanent checkpoint. Based on mutable checkpoints, our nonblocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on the stable storage.
---
paper_title: The Performance of Consistent Checkpointing

paper_content:

Consistent checkpointing provides transparent fault tolerance for long-running distributed applications. Performance measurements of an implementation of consistent checkpointing are described. The measurements show that consistent checkpointing performs remarkably well. Eight computation-intensive distributed applications were executed on a network of 16 diskless Sun-3/60 workstations, and the performance without checkpointing was compared to the performance with consistent checkpoints taken at two-minute intervals. For six of the eight applications, the running time increased by less than 1% as a result of the checkpointing. The highest overhead measured was 5.8%. Incremental checkpointing and copy-on write checkpointing were the most effective techniques in lowering the running time overhead. It is argued that these measurements show that consistent checkpointing is an efficient way to provide fault tolerance for long-running distributed applications. >
---
paper_title: Checkpointing and rollback-recovery algorithms in distributed systems

paper_content:

To keep it free of arbitrary failures, a distributed system may require taking checkpoints from time to time. In case of failures, the system will roll back to checkpoints where global consistency is preserved. Based on the concept of global consistency defined in this article, which eliminates both received-not-sent and sent-not-received types of inconsistencies, we developed a synchronous checkpointing algorithm C∗ and an asynchronous roll back-recovering algorithm R∗ with O(VE) message complexity, which has a relatively small coefficient, where V is the number of processors and E is the number of communication links in the system. Neither incoming message logging nor message-number calculation is needed. Our algorithms work well in complicated situations such as communication loops involving a minimal number of processors. Because of the feature of instant crash recovery and the overall low time, space, and message complexities, these algorithms are most feasible in real-time applications where rapid rollback recovery is crucial.
---
paper_title: Adaptive recovery for mobile environments

paper_content:

Mobile computing allows ubiquitous and continuous access to computing resources while the users travel or work at a client’s site. The flexibility introduced by mobile computing brings new challenges to the area of fault tolerance. Failures that were rare with fixed hosts become common, and host disconnection makes fault detection and message coordination difficult. This paper describes a new checkpoint protocol that is well adapted to mobile environments. The protocol uses time to indirectly coordinate the creation of new global states, avoiding all message exchanges. The protocol uses two different types of checkpoints to adapt to the current network characteristics, and to trade off performance with recovery time.
---
paper_title: A Checkpointing Algorithm for Mobile Computing Environment

paper_content:

Mobile computing is going to change the way, computers are used today. However mobile computing environment has features like high mobility, frequent disconnections, and lack of resources, such as memory and battery power. Such features make applications, running on mobile devices, more susceptible to faults. Checkpointing is a major technique to confine faults and restart applications faster. In this paper, we present a coordinated checkpointing algorithm for deterministic applications. We are using anti-messages along-with selective logging to achieve faster recovery and reduced energy consumption. Our algorithm is non-blocking in nature and avoids unnecessary computation. We ask only minimum number of processes to take the checkpoint and also take in to account the limited storage available at mobile devices.
---
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: 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: Low-Cost Checkpointing and Failure Recovery in Mobile Computing Systems

paper_content:

A mobile computing system consists of mobile and stationary nodes, connected to each other by a communication network. The presence of mobile nodes in the system places constraints on the permissible energy consumption and available communication bandwidth. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system (checkpoint) is required. Locating mobile nodes contributes to the checkpointing and recovery costs. Synchronous snapshot collection algorithms, designed for static networks, either force every node in the system to take a new local snapshot, or block the underlying computation during snapshot collection. Hence, they are not suitable for mobile computing systems. If nodes take their local checkpoints independently in an uncoordinated manner, each node may have to store multiple local checkpoints in stable storage. This is not suitable for mobile nodes as they have small memory. This paper presents a synchronous snapshot collection algorithm for mobile systems that neither forces every node to take a local snapshot, nor blocks the underlying computation during snapshot collection. If a node initiates snapshot collection, local snapshots of only those nodes that have directly or transitively affected the initiator since their last snapshots need to be taken. We prove that the global snapshot collection terminates within a finite time of its invocation and the collected global snapshot is consistent. We also propose a minimal rollback/recovery algorithm in which the computation at a node is rolled back only if it depends on operations that have been undone due to the failure of node(s). Both the algorithms have low communication and storage overheads and meet the low energy consumption and low bandwidth constraints of mobile computing systems.
---
paper_title: Use of common time base for checkpointing and rollback recovery in a distributed system

paper_content:

An approach to checkpointing and rollback recovery in a distributed computing system using a common time base is proposed. A common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with the idea of pseudo-recovery points to develop a checkpointing algorithm that has the following advantages: reduced wait for commitment for establishing recovery lines, fewer messages to be exchanged, and less memory requirement. These advantages are assessed quantitatively by developing a probabilistic model. >
---
paper_title: Low overhead optimal checkpointing for mobile distributed systems

paper_content:

A checkpoint algorithm for a mobile distributed computing system (MDCS) needs to handle many new issues like: mobility, low bandwidth of wireless channels, lack of stable storage on mobile nodes, disconnections, limited battery power and high failure rate of mobile nodes. These issues make traditional checkpointing techniques unsuitable for mobile distributed systems. Coordinated checkpointing may be useful to checkpoint MDCS if it is nonblocking and require minimum number of processes to checkpoint. Cao and Singhal [G. Cao et al., (2001)] achieved both by introducing the concept of mutable checkpoints. Many of these mutable checkpoints may be useless. We propose a nonblocking minimum process coordinated checkpointing protocol that not only minimizes useless checkpoints but also minimizes overall bandwidth required over wireless channels.
---
paper_title: A non-intrusive minimum process synchronous checkpointing protocol for mobile distributed systems

paper_content:

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channels, high mobility and limited battery life. These issues make traditional checkpointing algorithms unsuitable for checkpointing mobile distributed systems. Minimum process coordinated checkpointing is a good approach to introducing fault tolerance in a distributed system transparently. This approach is domino-free and requires at most two checkpoints of each process on stable storage, and forces only interacting processes to checkpoint. Sometimes, it also requires piggybacking of information onto normal messages, blocking of the underlying computation or taking some useless checkpoints. In this paper, we propose a non-intrusive minimum process synchronous checkpointing protocol for mobile distributed systems, where only the minimum number of tentative checkpoints is taken. We also optimize the number of useless forced (mutable) checkpoints and message overheads as compared to Cao et al. (2001).
---
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: Hybrid checkpoint protocol for supporting mobile-to-mobile communication

paper_content:

Some information systems consist of mobile stations and fixed stations. Mission critical applications are required to execute fault-tolerance in these systems. However, the mobile stations support neither enough volume of storage, processing power nor battery capacity to provide reliable communication and computation. Thus, it is difficult for multiple mobile stations to synchronously take checkpoints. We propose a hybrid checkpointing protocol where mobile stations take asynchronously and fixed ones take synchronously checkpoints. In addition, mobile stations store messages into logs for making the local states consistent with checkpoints taken by fixed stations. For supporting wireless LAN protocols such as IEEE 802.11 and HIPERLAN, messages are stored into a log in a mobile support station without exchanging additional messages even with mobile-to-mobile communication.
---
paper_title: PITFALLS IN DISTRIBUTED NONBLOCKING CHECKPOINTING

paper_content:

Coordinated checkpointing has low stable storage requirements and simplifies the recovery process by reserving a set of consistent global checkpoints. Unfortunately, most algorithms that were proposed either incurred a high communication overhead or blocked all processes. Then, a coordinated algorithm was presented which was nonblocking and which forced only a subset of all processes to participate in a checkpointing event. This algorithm was shown to create inconsistencies in some situations and new algorithms to take consistent checkpoints were proposed. However, we found that these algorithms can still result in inconsistencies when typical behavior in a distributed environment is considered, such as multiple forced checkpoints and multiple concurrent checkpoint initiations. In this paper we identify the inconsistencies that can occur and present an efficient nonblocking algorithm that collects consistent global checkpoints and avoids some of the pitfalls in distributed nonblocking checkpointing.
---
paper_title: Mutable checkpoints: a new checkpointing approach for mobile computing systems

paper_content:

Mobile computing raises many new issues such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. Coordinated checkpointing is an attractive approach for transparently adding fault tolerance to distributed applications since it avoids domino effects and minimizes the stable storage requirement. However, it suffers from high overhead associated with the checkpointing process in mobile computing systems. Two approaches have been used to reduce the overhead: First is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process nonblocking. These two approaches were orthogonal previously until the Prakash-Singhal algorithm combined them. However, we found that this algorithm may result in an inconsistency in some situations and we proved that there does not exist a nonblocking algorithm which forces only a minimum number of processes to take their checkpoints. In this paper; we introduce the concept of "mutable checkpoint," which is neither a tentative checkpoint nor a permanent checkpoint, to design efficient checkpointing algorithms for mobile computing systems. Mutable checkpoints can be saved anywhere, e.g., the main memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring large amounts of data to the stable storage at MSSs over the wireless network. We present techniques to minimize the number of mutable checkpoints. Simulation results show that the overhead of taking mutable checkpoints is negligible. Based on mutable checkpoints, our nonblocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on the stable storage.
---
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: Lazy checkpoint coordination for bounding rollback propagation

paper_content:

The technique of lazy checkpoint coordination, which preserves process autonomy while employing communication-induced checkpoint coordination for bounding rollback propagation is proposed. The notion of laziness is introduced to control the coordination frequency and allow a flexible tradeoff between the cost of checkpoint coordination and the average rollback distance. Worst-case overhead analysis provides a means for estimating the extra checkpoint overhead. Communication trace-driven simulation for several parallel programs is used to evaluate the benefits of the proposed scheme. >
---
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. >
---

Title: A Review of Fault Tolerant Checkpointing Protocols for Mobile Computing Systems

Section 1: INTRODUCTION
Description 1: Write about the importance of fault tolerance in distributed computing systems, the types of faults, and the general techniques used for fault tolerance, emphasizing the role of checkpointing.

Section 2: CHECKPOINTING
Description 2: Explain what checkpointing is, how it works in distributed systems, the concept of consistent global states, and the necessity of restoring from previous states after failures.

Section 3: ASPECTS OF CHECKPOINTING
Description 3: Discuss various aspects relevant to checkpointing like the frequency of checkpointing, contents of a checkpoint, overheads of checkpointing algorithms, and different applications of checkpointing.

Section 4: CHECKPOINTING ISSUES
Description 4: Identify the unique challenges and issues that arise in checkpointing for mobile nodes and the distributed systems they inhabit, including mobility, disconnections, energy constraints, and lack of stable storage.

Section 5: RELATED CONCEPTS
Description 5: Cover related concepts and terminologies such as dependency between processes, local and global checkpoints, rollback recovery, and different message complexities in checkpointing algorithms.

Section 6: RELATED WORK
Description 6: Review and summarize previous work and literature on fault-tolerant checkpointing, specifically focusing on various proposed algorithms, their methodologies, and their application in both static and mobile environments.