Routing on butterfly networks with random faults


Journal Article

In this paper we show that even if every node or edge in an N-node butterfly network fails independently with some constant probability, p, it is still possible to identify a set of Θ(N) nodes between which packets can be routed in any permutation in O(log N) steps, with high probability. Although the analysis is complicated, the routing algorithm itself is relatively simple.

Duke Authors

Cited Authors

  • Cole, R; Maggs, B; Sitaraman, R

Published Date

  • December 1, 1995

Published In

Start / End Page

  • 558 - 570

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus