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(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–&OHgr;(loglog 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). We also give a simple constant-degree construction with O(N) nodes that tolerates O(N(1–2-d)/d worst case faults.

REFERENCES

• AAB+92: M. Ajtai, N. Alon, J. Bruck, R. Cypher, C.T. Ho, M. Naor, and E. Szemerddi. Fault tolerant graphs, perfect hash functions and disjoin# paths. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 693-702, 1992.
• AC88: N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
• AKS82: M. Ajtai, J. Komlds, and E. Szemerddi. Largest random component of a k-cube. Combinatorica, 2(1):1-7, 1982.
• AL91: Bill Aiello , Tom Leighton, Coding theory, hypercube embeddings, and fault tolerance, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.125-136, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113391]
• BCH91: J. Bruck, R. Cypher, and C.-T. Ho. Faulttolerant meshes and hypercubes with minimal number of spares. Technical Report RJ 8211, IBM, July 1991.
• BCH92a: J. Bruck, R. Cypher, and C.-T. Ho. Faulttolerant de Bruijn and shuffle-exchange networks. In Proceedings of the 1992 In#ernational Conference on Parallel Processing, 1992.
• BCH92b: J. Bruck, R. Cypher, and C.-T. Ho. Tolerating faults in a mesh with a row of spare nodes. In Proceedings of the 4#h IEEE Symposium on Parallel and Distributed Processing, 1992.
• BCH93: Jehoshua Bruck , Robert Cypher , Ching-Tien Ho, Fault-tolerant meshes with small degree, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.1-10, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165232]
• CMS93: Richard Cole , Bruce Maggs , Ramesh Sitaraman, Multi-scale self-simulation: a technique for reconfiguring arrays with faults, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.561-572, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167235]
• DH90: Shantanu Dutt , J. P. Hayes, On Designing and Reconfiguring k-Fault-Tolerant Tree Architectures, IEEE Transactions on Computers, v.39 n.4, p.490-503, April 1990 [doi>10.1109/12.54842]
• FKP91: P. Fraignisud, C. Kenyon, and A. Pelc. Finding a target subnetwork in sparse network with random faults. Technical report, Lsboratoir de l'Informatique du Parallelisme, 1991.
• HLN89: J. Hastad , T. Leighton, Fast computation using faulty hypercubes, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.251-263, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73031]
• KKL+90: C. Kaklamanis, A.R. Karlin, F.T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C. Thomborson, and A. Tsantilas. Asymptotically tight bounds for computing with faulty arrays of processors. In Proceedings of #he 31s# Annual Symposium on Foundations of Computer Science, pages 285-296. IEEE, 1990.
• KNT94: Anna R. Karlin , Greg Nelson , Hisao Tamaki, On the fault tolerance of the butterfly, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.125-133, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195117]
• LM92: F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992 [doi>10.1109/12.142684]
• LMS92: F. T. Leighton, B. Maggs, and R. Sitarsman. On the unexpected fault-tolerance of some popular bounded-degree networks. In Proceedings of the 33d Annual Symposium on Foundations of Computer Science, pages 542-552. IEEE, 1992.
• Rag89: P. Raghavan, Robust algorithms for packet routing in a mesh, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.344-350, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72972]
• Tam92a: H. Tamaki. Efficient self-embedding of butterfly networks with random faults. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 533-541, 1992.
• Tam92b: Hisao Tamaki, Robust bounded-degree networks with small diameters, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.247-256, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141866]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  G. Mathematics of Computing

General Terms:
Theory, Verification