John Turek, Walter Ludwig, et al.
SPAA 1994
Suppose each node and each edge of a network is independently faulty with probability at most p and q respectively, where 0 < p, q < 1 are arbitrary constants independent of the size of the network. For each fixed integer d > 2, we construct a network with O(N) nodes and with degree O(loglog N) such that, after removing all the faulty nodes and edges, it still contains the N-node d-dimensional N1/d × ... × Nx/d torus, and hence the mesh of the same size, with probability 1 - N-ω(loglogN). This is derived as a consequence of a simple const ant-degree construction which tol erates random faults where the failure probability of each node is O(log-3d JV). We also give a simple constant-degree construction with O(N) nodes that tolerates O(N1-2-d)/d) worst case faults.
John Turek, Walter Ludwig, et al.
SPAA 1994
Christos H. Papadimitriou, Prabhakar Raghavan, et al.
FOCS 1994
Anna R. Karlin, Greg Nelson, et al.
STOC 1994
Christos H. Papadimitriou, Prabhakar Raghavan, et al.
Journal of Computer and System Sciences