Fault tolerance in hypercube-derivative networks
Fred S. Annexstein · 1989
We present algbri~hms which reconfigure faulty deBruijn and Butterfly networks.We show that, with high probability, an N-node deBruijn (resp., Butterfly) network with uniformly distributed faulty processors can simulate a fault-free N-node deBrnijn (resp., Butterfly) network with a slowdown factor of O(loglogN).Our configuration algorithm is deterministic, operates in a distributed fashion, uses only local control, and takes time O (log 2 N). INTRODUCTIONIn any VLSI implementation of a large-scale computer network, some positive fraction of the processing elements are likely to contain faults.l~ecent work of Hastad, Leighton, and Newman [6] has shown that the hypercube has a strong fault-tolerance property: an N-node hypercube with a constant fraction of randomly distributed processor failures can still, with probability 1 -O(1/N), simulate the computation of a fault-free N-node hypercube, with only a constant factor slowdown in total pro-