Efficient algorithms for selection of recovery points in tree task models

Author

Mishra, Subhada K. ; Raghavan, Vijay V. ; Tzeng, Nian-Feng

Author_Institution

Center for Adv. Comput. Studies, Southwestern Louisiana Univ., Lafayette, LA, USA

Volume

17

Issue

7

fYear

1991

fDate

7/1/1991 12:00:00 AM

Firstpage

731

Lastpage

734

Abstract

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₂), where N is the number of tasks, while previously reported procedures have exponential time requirements. The results are generalized for an arbitrary tree model

Keywords

computational complexity; optimisation; trees (mathematics); arbitrary tree model; binary tree model; exponential time requirements; recovery points; task precedence; time complexity; tree structure; tree task models; uniprocessor environment; Availability; Binary trees; Computational modeling; Databases; Dynamic programming; Fault tolerant systems; Software algorithms; Software systems; Tree data structures; Tree graphs;

fLanguage

English

Journal_Title

Software Engineering, IEEE Transactions on

Publisher

ieee

ISSN

0098-5589

Type

jour

DOI

10.1109/32.83909

Filename

83909