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

Research output: Contribution to journalArticle

1 Citation (Scopus)


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 N1/d× ... ×N1/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-3dN). We also give a simple constant-degree construction with O(N) nodes that tolerates O(N(1-2-d)/d) worst case faults.

Original languageEnglish
Pages (from-to)371-379
Number of pages9
JournalJournal of Computer and System Sciences
Issue number3
Publication statusPublished - 1996

Fingerprint Dive into the research topics of 'Construction of the mesh and the torus tolerating a large number of faults'. Together they form a unique fingerprint.

  • Cite this