• 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, pp. 1303-1333.

  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.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page