Construction of the Mesh and the Torus Tolerating a Large Number of Faults

✍ Scribed by Hisao Tamaki

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 835 KB
• Volume: 53
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0076

✦ Synopsis

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 &0 (log 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.