Sparse networks tolerating random faults

Proposes a general method to construct a fault-tolerant network G*, for any network G with N processors, such that G* has O(N) processors and contains a fault-free isomorphic copy of G with high probability, even if processors fail independently with constant probability. Based on the construction, we also show that we can construct such fault-tolerant networks with O(N) processors and O(M log N) communication links for a circulant network, a hypercube, a de Bruijn network, a shuffle-exchange network, and cube-connected cycles with N processors and M communication links