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.>

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.>