Fully-scalable fault-tolerant simulations for BSP and CGM

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_h p)²) (resp. O(log_h p)) slowdown per communication round, provided that a deterministic preprocessing is done that requires O((log_h p) ²) communication rounds and linear (in h) computation per processor in each communication round. Our results are fully-scalable over all values of p from θ(1) to θ(n). Furthermore, our results imply that for p⩽n^ε (ε<1), algorithms can be made resilient to a constant fraction of processor faults without any asymptotic slowdown