- On the fault tolerance of some popular bounded-degree
networks. F. T. Leighton, B. M. Maggs, and R. K. Sitaraman,
SIAM Journal on Computing, Volume 27, Number 5, October 1998,
- In this paper, we study the ability of butterfly, shuffle-exchange,
and mesh of trees networks to tolerate faults. We show that an
N-node butterfly containing N^(1-epsilon) worst-case faults (for
any constant epsilon > 0) can emulate a fault-free butterfly of the
same size with only constant slowdown. A similar result is proved for
the shuffle-exchange graph. Previously, no connected bounded-degree
networks were known to be able to sustain more than a constant number of
worst-case faults without suffering more than a constant-factor
slowdown in performance. We also show that an N-node butterfly
whose nodes fail with some constant probability p can emulate a
fault-free N-node butterfly with a slowdown of 2^O(log* N).
The proofs of these results combine the technique of redundant
computation with new algorithms for routing packets around faults.
Techniques for tolerating up to log^O(1) N worst-case faults on
butterflies and meshes of trees that do not rely on redundant
computation are also presented.
- Back to other
- Back to my home page