Efficient computations on fault-prone BSP machines
Spyros C. Kontogiannis, Grammati E. Pantziou, Paul G. Spirakis · 1997
In this paper general simulations of algorithms designed for fully operational BSP machines on BSP machines with faulty processors or unavailable processors are developed. The fail-stop model is considered, that is, if a processor fails or becomes unavailable it remains so until the end of the computation. The faults are random, that is, a processor may fail independently with probablility a, a is a constant. Two possible settings for fault occurence are considered: the faults are either static (the faulty or unavailable processors are already known at the start of the computation) or dynamic (the processors become faulty or unavailable during the computation). In the case of static faults, a simulation of an n-processor fault-free BSP machine on a faulty n-processor BSP machine is presented with constant slowdown per local computation step and O(log n \\Delta maxfL; gg) slowdown per communication step, given that a preprocessing has been done that needs O(log 2 n \\Delta maxfL; gg)...