RACE: a software-based fault tolerance scheme for systematically transforming ordinary algorithms to robust algorithms

We propose the robust algorithm-configured emulation (RACE) scheme for efficient parallel computation and communication in the presence of faults. A wide variety of algorithms originally designed for fault-free meshes, tori, and k-ary n-cubes can be transformed to corresponding robust algorithm through RACE. In particular optimal robust algorithms can be derived for total exchange (TE) and ascend/descend operations with a factor of 1+o (1) slowdown. Also, RACE can tolerate a large number of faulty elements, without relying on hardware redundancy or any assumption about the availability of a complete subarray