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)
| Page Owner: John Bazik | Last Modified: Fri Feb 9 17:44:32 2007 |