Title :
Recovery point selection on a reverse binary tree task model
Author :
Chen, Shyh-Kwei ; Tsai, W.T. ; Thuraisingham, M. Bhavani
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fDate :
8/1/1989 12:00:00 AM
Abstract :
An analysis is conducted of 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, an optimal placement algorithm is proposed. For multiprocessor systems, a procedure for computing their performance is described. Since no closed form solution is available, an alternative measurement is proposed that has a closed form formula. On the basis of this formula, algorithms are devised for solving the recovery point placement problem. The estimated formula can be extended to include communication delays where the algorithm devised still applies
Keywords :
computational complexity; fault tolerant computing; multiprocessing systems; trees (mathematics); arbitrary reverse tree model; closed form formula; closed form solution; communication delays; computation time minimization; multiprocessor systems; optimal placement algorithm; performance computation procedure; recovery point placement problem; recovery point selection; reverse binary tree task model; uniprocessor systems; Binary trees; Closed-form solution; Computational modeling; Computer science; Delay estimation; Fault detection; Helium; Multiprocessing systems; Sequential analysis; Testing;
Journal_Title :
Software Engineering, IEEE Transactions on