On the performance of parallel algorithms on a gracefully degrading system achieved through the BSPM

The Bulk Synchronous Parallel Model (BSPM) proposed by Valiant [10] can be used to construct a gracefully degrading system, as described in [7]. We show that by using the BSPM as a cost model we can estimate an upper bound on the overhead introduced to achieve a gracefully degrading system. The effect of processor failures on the performance of such a system is considered in terms of the parameters of the model. We show that we can estimate in advance the behaviour and degree of the degradation we are likely to see. Experimental results from an implementation of the approach in [7] on an MPP are used to illustrate the predictions. 1 Introduction A key problem that MPPs face is reliability. The huge number of components that make them up, even if they have an extremely long Mean Time Between Failure (MTBF) means that the MTBF of the entire system will be low, perhaps counted in terms of hours. The sheer redundancy an MPP exhibits, however, should make it possible to incorporate fault-t..