Effects of checkpointing and queueing on program performance

Checkpointing is a technique for reducing the completion (execution) time of long-running batch programs in the presence of failures. It consists of intermittently saving the current status of the program under execution so that if a failure occurs, the program needs to be restarted from the most recent checkpoint rather than from the beginning. Because of occasional long reprocessing times and the possibility of failures during recovery, checkpoints during reprocessing is guaranteed to increase the effectiveness of any checkpointing technique. In all models considered thus far, checkpointing is allowed only during useful processing of the program. In this paper, the authors carry out the analysis of a model with checkpointing during reprocessing following failures. Closed-form expressions for the Laplace transform of the program completion time, its mean and variance are derived. It is shown that, asymptotically, the expected completion time increases linearly (exponentially) with the service requirement in the presence (absence) of checkpointing. The question of whether checkpointing is beneficial is addressed and the optimal checkpointing rate, α*, which minimizes the expected completion time, is computed.