A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches


Journal Article

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

Full Text

Duke Authors

Cited Authors

  • Maggs, BM; Goldberg, AV; Plotkin, SA

Published Date

  • January 1, 1994

Published In

Volume / Issue

  • 43 / 3

Start / End Page

  • 321 - 326

International Standard Serial Number (ISSN)

  • 0018-9340

Digital Object Identifier (DOI)

  • 10.1109/12.272432

Citation Source

  • Scopus