About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
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.