Publications [#236686] of Bruce Maggs

Journal articles or Book chapters PUBLISHED

1. Maggs, BM; Goldberg, AV; Plotkin, SA, A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches, IEEE Transactions on Computers, vol. 43 no. 3 (January, 1994), pp. 321-326, Institute of Electrical and Electronics Engineers (IEEE) [doi]
   (last updated on 2024/04/23)

   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 O(logN) time. After reconfiguration, the multibutterfly 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(logN) time. © 1994 IEEE