Reconfiguring a hypercube in the presence of faults

Publisher Website
Google Scholar
Abstract
We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. In particular, we describe algorithms for embedding an N/2-node hypercube in an N-node hypercube with faulty processors. Provided that the processors of the N-node hypercube are faulty with probability p N/2-node hypercube are mapped to functioning cells at distance 3 or less apart in the N-node hypercube. The algorithm is deterministic, easy to implement and runs in &Ogr;(log N) steps using only local control. We also describe ways to produce embeddings which allow for low delay simulations, as well as ways to use a faulty hypercube to efficiently simulate a completely functioning hypercube of the same size.

This publication has 0 references indexed in Scilit: