Fully-scalable fault-tolerant simulations for BSP and CGM
Sung‐Ryul Kim, Kunsoo Park · 2003
In this paper we consider general simulations of algorithms designed for fully operational BSP and CGM machines on machines with faulty processors. The faults are deterministic (i.e., worst-case distributions of faults are considered) and static (i.e., they do not change in the course of computation). We assume that a constant fraction of processors are faulty. We present a deterministic simulation (resp. a randomized simulation) that achieves constant slowdown per local computations and O((log/sub h/ p)/sup 2/) (resp. O(log/sub h/ p)) slowdown per communication round, provided that a deterministic preprocessing is done that requires O((log/sub h/ p)/sup 2/) communication rounds and linear (in h) computation per processor in each communication round. Our results are fully-scalable over all values of p from /spl theta/(1) to /spl theta/(n). Furthermore, our results imply that for p/spl les/n/sup /spl epsi// (/spl epsiv/<1), algorithms can be made resilient to a constant fraction of processor faults without any asymptotic slowdown.