Fault tolerance in hypercube-derivative networks (preliminary version)
Fred S. Annexstein · ACM SIGARCH Computer Architecture News · 1991
We present algorithms 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 deBruijn (resp., Butterfly) network with a slowdown factor of O (log log N ). Our configuration algorithm is deterministic, operates in a distributed fashion, uses only local control, and takes time O (log 2 N ).