Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 558-570 |
| Number of pages | 13 |
| Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
| State | Published - 1995 |
| Event | Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA Duration: Oct 23 1995 → Oct 25 1995 |
ASJC Scopus subject areas
- Hardware and Architecture