On tolerating faults in naturally redundant algorithms

A class of algorithms suitable for fault-tolerant execution in multiprocessor systems by exploiting the existing embedded redundancy in the problem variables is characterized. Because of this unique property, no extra computations need be superimposed on the algorithm in order to provide redundancy for fault recovery, as well as fault detection in some cases. A forward recovery scheme is thus used with very low time overhead. The method is applied to the implementation of two iterative algorithms: solution of Laplace equations by Jacobi´s method and the calculation of the invariant distribution of a Markov chain. Experiments show less than 15% performance degradation for significant problem instances in fault-free situations, and as low as 2.43% in some cases. The extra computation time needed for locating and recovering from a detected fault does not exceed the time necessary to execute a single iteration. The fault-detection procedures provide fault coverage close to 100% for faults causing errors that affect the correctness of the computations