Skip to main content

Routing on butterfly networks with random faults

Publication ,  Journal Article
Cole, R; Maggs, B; Sitaraman, R
Published in: Annual Symposium on Foundations of Computer Science - Proceedings
December 1, 1995

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 Scholars

Published In

Annual Symposium on Foundations of Computer Science - Proceedings

ISSN

0272-5428

Publication Date

December 1, 1995

Start / End Page

558 / 570
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cole, R., Maggs, B., & Sitaraman, R. (1995). Routing on butterfly networks with random faults. Annual Symposium on Foundations of Computer Science - Proceedings, 558–570.
Cole, R., B. Maggs, and R. Sitaraman. “Routing on butterfly networks with random faults.” Annual Symposium on Foundations of Computer Science - Proceedings, December 1, 1995, 558–70.
Cole R, Maggs B, Sitaraman R. Routing on butterfly networks with random faults. Annual Symposium on Foundations of Computer Science - Proceedings. 1995 Dec 1;558–70.
Cole, R., et al. “Routing on butterfly networks with random faults.” Annual Symposium on Foundations of Computer Science - Proceedings, Dec. 1995, pp. 558–70.
Cole R, Maggs B, Sitaraman R. Routing on butterfly networks with random faults. Annual Symposium on Foundations of Computer Science - Proceedings. 1995 Dec 1;558–570.

Published In

Annual Symposium on Foundations of Computer Science - Proceedings

ISSN

0272-5428

Publication Date

December 1, 1995

Start / End Page

558 / 570