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