Tech Report CS-92-23

Fault-Tolerant and Efficient Parallel Computation

Alexander Allister Shvartsman

April 1992


Recent advances in computer technology made parallel machines a reality. Massively parallel systems use many general-purpose, inexpensive processing elements to attain computation speed-ups comparable to or better than those achieved by expensive, specialized machines with a small number of fast processors. In such setting, however, one would expect to see an increased number of processor failures attributable to hardware or software. This may eliminate the potential advantage of parallel computation. We believe that this presents a reliability bottleneck that is among fundamental problems in parallel computation.

We investigate {\em algorithmic ways of introducing fault-tolerance in multiprocessors under the constraint of preserving efficiency}. This research demonstrates how in certain models of parallel computation it is possible to combine efficiency and fault-tolerance. We show that in the models we study, it is possible to develop efficient parallel algorithms without concern for fault-tolerance, and then correctly and efficiently execute these algorithms on parallel machines whose processors are subject to arbitrary dynamic fail-stop errors. By ensuring efficient executions for any patterns of failures, the efficiency is also maintained when failures are infrequent, or when the expected number of failures is small.

The efficient algorithmic approaches to multiprocessor fault-tolerance presented in this thesis make a contribution towards bridging the gap between the abstract models of parallel computation and realizable parallel architectures.

(complete text in pdf or gzipped postscript)