Parallel Algorithm for Reconfiguring a Multibutterfly Network with FaultySwitches

摘要

This paper describes a deterministic algorithm for reconfiguring a multibutterflynetwork 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 O(log N) time.