- A parallel algorithm for reconfiguring a multibutterfly
network with faulty switches. A. V. Goldberg, B. M. Maggs, and S. A.
Plotkin, IEEE Transactions on Computers, Vol. 43, No. 3, March 1994,
- This paper describes a deterministic algorithm for reconfiguring a
multibutterfly network with faulty switches. Unlike previous
reconfiguration algorithms, this one is performed entirely by the
switches of 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.
After reconfiguration, the network can tolerate f worst-case
faults and still route any permutation between some set of N-O(f)
inputs and N-O(f) outputs in O(log N) time.
- Back to other
- Back to my home page