eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6386
Title:  On the Optimum Checkpoint Selection Problem 
Authors:  Toueg, Sam Babaoglu, Ozalp 
Keywords:  computer science technical report 
Issue Date:  Feb1983 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83546 
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 $ni$ 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. 
URI:  http://hdl.handle.net/1813/6386 
Appears in Collections:  Computer Science Technical Reports

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