Construction of the mesh and the torus tolerating a large number of faults

Abstract

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.