Concise Papers Efficient Algorithms For Selection of Recovery Points in lkee Task Models
Subhada K. Mishra, Vijay V. Raghavan, Nian-Feng Tzeng · 1991
Absfruct-In this note we develop efficient solutions to the problem of optimally selecting recovery points. These 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. For the binary tree model, an algorithm to minimize the expected computation time of the task system under a uniprocessor environment has been developed. The algorithm has time complexity of O(N’), where N is the number of tasks, while previously reported procedures have exponential time requirements. The results have been generalized for an arbitrary tree model. Index Terms-Checkpoints, dynamic programming, emr recovery, reliability, rollback.