Experimental Evaluation of Techniques for Fault Tolerance
Luiz A.F. Laranjeira, Miroslaw Malek, Roy M. Jenevein · 1992
In the design of critical applications that must deliver continuous service under real-time constraints it is of essence to have fault tolerance achieved with as low time redundancy as possible. Furthermore, in the case of embedded systems, space may also be a limited resource. Therefore, for critical applications, we are left with the task of providing reliable computing with low space and time redundancy. The quantification of space and time redundancy in the implementation of fault tolerance is consequently a must. We present the results of practical experiments, implemented on a multiprocessor platform, with several general and application-specific technique for fault tolerance. The time and space overheads incurred by each technique are analyzed and compared. Three iterative algorithms were utilized in the experiments: solution of Laplace equations, the calculation of the invariant distribution of Markov chains, and the solution of systems of linear equations. Fault-tolerant versions of those algorithms were implemented with two general techniques for fault tolerance (triplication with voting and checkpointing and rollback) and three application-specific techniques for fault tolerance (self stabilization, algorithm-based fault tolerance, and natural redundancy). The results of the experiments show that the approach based on natural redundancy, for applications possessing that property, presents the most attractive cost/benefit ratio when only single faults are likely to occur. The implementations of the above-mentioned algorithms with this technique demanded less than 15% time redundancy for problems of significant size in fault-free situations, only one extra iteration to recover from a fault, and no extra processors. These capabilities seem ideal for critical applications that must deliver reliable service in a timely manner. Surprisingly, time overheads for some other methods were much higher than expected.