Fault-Tolerant and Efficient Parallel Computation
Abstract
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 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 failstop 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1992
- Accession Number
- ADA253350
Entities
People
- Alexander A. Shvartsman
Organizations
- Brown University