Efficient algorithms for selection of recovery points in tree task models
Subhada K. Mishra, Vijay V. Raghavan, Nian-Feng Tzeng · IEEE Transactions on Software Engineering · 1991
Efficient solutions to the problem of optimally selecting recovery points are developed. The solutions are intended for models of computation in which task precedence has a tree structure and a task may fail due to the presence of faults. An algorithm to minimize the expected computation time of the task system under a uniprocessor environment has been developed for the binary tree model. The algorithm has time complexity of O(N/sub 2/), where N is the number of tasks, while previously reported procedures have exponential time requirements. The results are generalized for an arbitrary tree model.>