Routing on butterfly networks with random faults
Richard Cole, Bruce MacDowell Maggs, Ramesh K. Sitaraman · 2002
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 /spl Theta/(N) nodes between which packets can be routed in any permutation in O(logN) steps, with high probability. Although the analysis as complicated, the routing algorithm itself is relatively simple.