Scholars@Duke

A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches

Publication ,  Journal Article
Maggs, BM; Goldberg, AV; Plotkin, SA
Published in: IEEE Transactions on Computers
January 1, 1994
Published version (DOI)

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

Duke Scholars

Bruce Maggs
Author Bruce Maggs Computer Science

Published In

IEEE Transactions on Computers

DOI

10.1109/12.272432

ISSN

0018-9340

Publication Date

January 1, 1994

Volume

43

Issue

3

Start / End Page

321 / 326

Related Subject Headings

  • Computer Hardware & Architecture
  • 4606 Distributed computing and systems software
  • 4009 Electronics, sensors and digital hardware
  • 1006 Computer Hardware
  • 0805 Distributed Computing
  • 0803 Computer Software
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Maggs, B. M., Goldberg, A. V., & Plotkin, S. A. (1994). A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches. IEEE Transactions on Computers, 43(3), 321–326. https://doi.org/10.1109/12.272432
Maggs, B. M., A. V. Goldberg, and S. A. Plotkin. “A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches.” IEEE Transactions on Computers 43, no. 3 (January 1, 1994): 321–26. https://doi.org/10.1109/12.272432.
Maggs BM, Goldberg AV, Plotkin SA. A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches. IEEE Transactions on Computers. 1994 Jan 1;43(3):321–6.
Maggs, B. M., et al. “A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches.” IEEE Transactions on Computers, vol. 43, no. 3, Jan. 1994, pp. 321–26. Scopus, doi:10.1109/12.272432.
Maggs BM, Goldberg AV, Plotkin SA. A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches. IEEE Transactions on Computers. 1994 Jan 1;43(3):321–326.

Published In

IEEE Transactions on Computers

DOI

10.1109/12.272432

ISSN

0018-9340

Publication Date

January 1, 1994

Volume

43

Issue

3

Start / End Page

321 / 326

Related Subject Headings

  • Computer Hardware & Architecture
  • 4606 Distributed computing and systems software
  • 4009 Electronics, sensors and digital hardware
  • 1006 Computer Hardware
  • 0805 Distributed Computing
  • 0803 Computer Software