**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.

- 1 Introduction
- 2 Butterflies and Multibutterflies
- 3 Routing around faults
- 4 Remarks
- References
- About this document ...

Mon Jul 22 19:56:03 EDT 1996