### Abstract

Suppose ach 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( log log N) such that, after removing all the faulty nodes and edges, it still contains the N-node d-dimensional N^{1/d}× ... ×N^{1/d} torus, and hence the mesh of the same size, with probability 1 - N^{-Ω(lof log N)}. This is derived as a consequence of a simple constant-degree construction which tolerates random faults, where the failure probability of each node is O(log^{-3d}N). We also give a simple constant-degree construction with O(N) nodes that tolerates O(N^{(1-2-d)/d}) worst case faults.

Original language | English |
---|---|

Pages (from-to) | 371-379 |

Number of pages | 9 |

Journal | Journal of Computer and System Sciences |

Volume | 53 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1996 |