• 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, pp. 321-326.

  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.

  HTML Postscript Compressed Postscript
  Back to other publications

  Back to my home page