Recovery Point Selection on a Reverse Binary Tree Task Model

In this paper we analyze the complexity of placing recovery points where the computation is modeled as a reverse binary tree task model. The objective is to minimize the expected computation time of a program in the presence of faults. The method can be extended to an arbitrary reverse tree model. For uniprocessor systems, we propose an optimal placement algorithm. For multiprocessor systems, we describe a procedure to compute its performance. Since no closed form solution is available, we propose an alternative measurement which has a closed form formula. Based upon this formula, we devise algorithms to solve the recovery point placement problem. The estimated formula can be extended to include communication delays where the algorithm devised still applies.