On the optimum checkpoint selection problem

We consider a model of computation consisting of a sequence of n tasks. In the absence of failures, each task i has a known completion time ti. Checkpoints can be placed between any two consecutive tasks. At a checkpoint, the state of the computation is saved on a reliable storage medium. Establishing a checkpoint immedi- ately before task i is known to cost si. This is the time spent in saving the state of the computation. When a failure is detected, the computation is restarted at the most recent checkpoint. Restarting the computation at checkpoint i requires restoring the state to the previously saved value. The time necessary for this action is given by ri. We derive an O(n 3 ) algorithm to select out of the n − 1 potential checkpoint locations those that result in the smallest expected time to complete all the tasks. An O(n 2 ) algorithm is described for the reasonable case where si > s j implies ri ≥ r j. These algorithms are applied to two models of failure. In the first one, each task i has a given probability pi of com- pleting without a failure, i.e., in time ti. Furthermore, failures occur independently and are detected at the end of the task during which they occur. The second model admits a continuous time failure mode where the failure intervals are independent and identically distributed random variables drawn from any giv en distribution. In this model, fail- ures are detected immediately. In both models, the algorithm also gives the expected value of the overall completion time and we show how to derive all the other moments. 1. Introduction. A variety of hardware and software techniques have been proposed to increase the reliability of computing systems that are inherently unreliable. One such soft- ware technique is rollback-recovery. In this scheme, the program is checkpointed from time to time by saving its state on secondary storage and the computation is restarted at the most recent checkpoint after the detection of a failure (6). Between the times when the failure is detected and the computation is restarted, the computation must be rolled back to the most recent checkpoint by restoring its state to the saved value. Obviously, rollback-recovery is an effective method only against transient failures. Examples of such failures are temporary hardware malfunctions, deadlocks due to resource contention, incorrect human interactions with the computation, and other external factors that can corrupt the computation's state. Per- sisting failures will block the computation no matter how many times it is rolled back. The ability to detect failures is an essential part of any fault-tolerance method including rollback- recovery. Examples of such failure detection methods are integrity assertion checking (8) and fail-stop processors (10). In the absence of checkpoints, the computation has to be restated from the beginning whenever a failure is detected. It is clear that with respect to many objectives such as mini- mum completion time, minimum recovery overhead, maximum throughput, etc., the position- ing of the checkpoints involves certain tradeoffs. A survey of an analytical framework for resolving some of these tradeoffs is presented by Chandy (1). Young (11) and Chandy et al (3) addressed the problem of finding the checkpoint interval so as to minimize the time lost due to recovery for a never-ending program subject to failures constituting a Poisson process. Gelenbe and Derochette (5) and Gelenbe (4) have generalized this result to allow the possibil- ity of external requests arriving during the establishment of a checkpoint or rollback-recovery.