Tolerating faults in hypercubes using subcube partitioning

Abstract

The authors examine the issue of running algorithms on a hypercube which has both node and edge faults, and they assume a worst-case distribution of the faults. It is proven that for any constant c, an n-dimensional hypercube (n-cube) with n/sup c/ faulty components contains a fault-tree subgraph that can implement a large class of hypercube algorithms with only a constant factor slowdown. In addition, the approach yields practical implementations for small numbers of faults. For example, it is shown that any regular algorithm can be implemented on an n-cube that has at most n-1 faults with slowdowns of at most two for computation and at most four for communication. This is the first result showing that an n-cube can tolerate more than O(n) arbitrarily placed faults with a constant factor slowdown.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>