Scholars@Duke

Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks

Publication ,  Journal Article
Leighton, FT; Maggs, BM
Published in: IEEE Transactions on Computers
January 1, 1992
Published version (DOI)

This paper describes simple deterministic O(log N) step algorithms for routing permutations of packets in multibutterflies and randomly-wired splitter networks. The algorithms are robust against faults (even in the worst case), and are efficient from a practical point of view. As a consequence, we find that the multibutterfly is an excellent candidate for a high-bandwidth low-diameter switching network underlying a shared-memory machine. © 1992 IEEE

Duke Scholars

Bruce Maggs
Author Bruce Maggs Computer Science
Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Transactions on Computers

DOI

10.1109/12.142684

ISSN

0018-9340

Publication Date

January 1, 1992

Volume

41

Issue

5

Start / End Page

578 / 587

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
Leighton, F. T., & Maggs, B. M. (1992). Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks. IEEE Transactions on Computers, 41(5), 578–587. https://doi.org/10.1109/12.142684
Leighton, F. T., and B. M. Maggs. “Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks.” IEEE Transactions on Computers 41, no. 5 (January 1, 1992): 578–87. https://doi.org/10.1109/12.142684.
Leighton FT, Maggs BM. Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks. IEEE Transactions on Computers. 1992 Jan 1;41(5):578–87.
Leighton, F. T., and B. M. Maggs. “Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks.” IEEE Transactions on Computers, vol. 41, no. 5, Jan. 1992, pp. 578–87. Scopus, doi:10.1109/12.142684.
Leighton FT, Maggs BM. Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks. IEEE Transactions on Computers. 1992 Jan 1;41(5):578–587.

Published In

IEEE Transactions on Computers

DOI

10.1109/12.142684

ISSN

0018-9340

Publication Date

January 1, 1992

Volume

41

Issue

5

Start / End Page

578 / 587

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