Loading...
Please wait, while we are loading the content...
Optimal Fault-tolerant Computing on Two Parallel Processors Optimal Fault-tolerant Computing on Two Parallel Processors
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bruno, J. Cooman, E. G. |
| Abstract | Suppose two identical processors, both subject to random failures, are available for running a single job of given duration. The failure law, whose mean is normalized to 1 for convenience, is operative only while a processor is active. To guard against the loss of accrued work due to a failure, checkpoints can be made, each requiring time ; a successful checkpoint saves the state of the computation, but failures can also occur during checkpoints. The problem is to determine how best to schedule checkpoints if the goal is to maximize the probability that the job nishes before both processors fail. We solve this problem under the assumption of an exponential failure law. In particular , for given and we show how to determine an integer k 0 and time intervals I 1 ; : : :; I k+1 such that an optimal procedure is to run the job on one machine, check-pointing at the end of each interval I j ; j = 1; : : :; k, until either the job is done or a failure occurs. In the latter case, the remaining processor resumes the job starting in the state saved by the last successful checkpoint; the job then runs until it completes or until the second processor also fails. We give an explicit formula for the maximum achievable probability of completing the job for any xed k 0. An explicit result for k opt , the optimum value of k, seems out of reach; however, we give upper and lower bounds on k opt that are remarkably tight; they show that only a few values of k need to be tested in order to nd k opt. We also derive the asymptotic estimate k opt ? q 2== = O(1) as ! 0 : Finally, we calculate conditional expected job completion times and discuss several open problems. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.comet.columbia.edu/~egc/webpapers/optimal.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
