Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: On the Optimum Checkpoint Selection Problem
Authors: Toueg, Sam
Babaoglu, Ozalp
Keywords: computer science
technical report
Issue Date: Feb-1983
Publisher: Cornell University
Abstract: 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 $t_{i}$. 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 immediately before task $i$ is known to cost $s_{i}$. 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 $r_{i}$. We derive an $O(n^{3})$ algorithm to select out of the $n-i$ 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 $s_{i} greater than s_{j}$ implies $r_{i} greater than r_{j}$. These algorithms are applied to two models of failure. In the first one, each task $i$ has a given probability $p_{i}$ of completing without a failure, i.e., in time $t_{i}$. 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 given distribution. In this model, failures 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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
83-546.pdf1.7 MBAdobe PDFView/Open
83-546.ps441.19 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us