Tech Report CS-89-49

Achieving Optimal CRCW PRAM Fault-Tolerance

Alex A. Shvartsman

December 1989

Abstract:

It is possible to combine efficiency and fault-tolerance in many PRAM algorithms in the presence of arbitrary dynamic fail-stop processor errors. Here we describe a technique for efficient and fault-tolerant simulations of {\em arbitrary} PRAM algorithms. Given a $P$-processor PRAM algorithm, we simulate it efficiently and fault-tolerantly by a $P ^ prime$-processor CRCW PRAM algorithm, for $P ^ prime ~ \leq ~ P$. The simulation is optimal for $P ^ prime ~ \leq ~ P / \log ^ 2 P $.

(complete text in pdf)