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 BSP (or CGM) machine is a parallel multicomputer consisting of p processors for which a memory of n words is evenly distributed and each processor can send and receive at most h messages in a superstep. 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 two fault-tolerant simulation techniques for BSP and CGM: 1. A deterministic simulation that achieves O(1) slowdown for local computations and O((log(h) p)(2)) slowdown for communications per superstep, provided that a preprocessing is done that requires O((log(h) p)(2)) supersteps and linear (in h) computation per processor in each superstep. 2. A randomized simulation that achieves O(1) slowdown for local computations and O(log(h) p) slowdown for communications per superstep with high probability, after the same (deterministic) preprocessing as above. Our results are fully scalable over all values of p from Theta (1) to Theta (n). Furthermore, our results imply that if p less than or equal to n(epsilon) for O    ((n/p)(delta)) for 0   less than or equal to 1 (which hold in almost all practical BSP and CGM computations), algorithms can be made resilient to a constant fraction of processor faults without any asymptotic slowdown. (C) 2000 Academic Press.
fault-tolerance bsp cgm generalized butterfly distance tree