Running algorithm efficiently on faulty hypercubes

Abstract

We examine the issue of running algorithms with a constant factor slowdown on a faulty hypercube in a worst case scenario. We present two set of novel results related to this issue. We first consider edge faults and show how to tolerate faults with a constant factor slowdown in communication and no slowdown in computation. The key to our approach is an efficient method for embedding a fault free Cube Connected Cycles (CCC) graph in the faulty hypercube. Using this embedding we can run ascend-descend algorithms (such as bitonic sort) on the faulty hypercube by implementing them on the embedded CCC. We then consider hypercubes with both edge and node faults. We prove that for any constant c there exists a fault-free subgraph of an n-dimensional hypercube with nc faulty components that can implement a large class of hypercube algorithms with only a constant factor slowdown. To the best of our knowledge, this result is the first in which a hypercube can tolerate more than O(n) faults in the worst case sense.