Andrew V. Goldberg
Bruce M. Maggs
Serge A. Plotkin
Abstract- This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the network, without the aid of any off-line computation, even though many of the switches may be faulty. The algorithm reconfigures an N-input multibutterfly network in time. After reconfiguratuion, the multibutterfly can tolerate f worst-case faults and still route any permutation between some set of inputs and outputs in time.