The design of fault-tolerant parallel algorithms
Luiz A.F. Laranjeira · 1992
This dissertation introduces a formal scheme, called NEST, for fault tolerance in multiprocessor systems, its theoretical and experimental validation, and a novel technique for fault tolerance based on natural algorithmic redundancy. NEST includes a formal comprehensive model and a design methodology for fault-tolerant parallel algorithms. The NEST model relies on the formalization of fault tolerance properties by means of three nested system predicates and their interrelationships. The NEST design methodology includes the analysis of system requirements related to fault tolerance, the exploitation of specific characteristics of applications that can facilitate fault tolerance and systematic design techniques to add fault tolerance properties to algorithms while preserving their functional characteristics. NEST is validated by the uniform application of its principles in the modeling of several well-known techniques for fault tolerance and in the design of fault-tolerant algorithms for specific problems. The novel approach for fault tolerance based on natural redundancy requires no computations to be superimposed to the original algorithm in order to insert redundancy for fault recovery, as well as for fault detection in some cases. Since redundancy for fault recovery comes free, forward recovery schemes can be employed with very low time overhead. This fact indicates that the approach is suitable for the design of responsive systems (which combine fault tolerance and real-time constraints). Furthermore, no additional processors are necessary in fault-free situations or to handle temporary faults. One disadvantage of the approach is that it is application dependent. Experimental validation for NEST is provided by the implementation in the Sequence Symmetry Multiprocessor of several examples consisting of three algorithms (the solution of Laplace equations, the calculation of the invariant distribution of Markov chains, and the solution of systems of linear equations) designed with five different techniques (triplication with voting, checkpointing and rollback, self stabilization, algorithm-based fault tolerance, and the approach based on natural redundancy). The time and space overheads incurred by each technique are analyzed and compared. The results of the experiments show that the approach based on natural redundancy presents the most attractive cost/benefit ratio when only single faults are likely to occur.