Embedding of rings in 2-D meshes and tori with faulty nodes

Abstract

To increase the reliability of networks embedded in meshes or tori and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in meshes and tori are necessary, In this paper, we present algorithms for embedding a ring in a mesh-type and torus-type multiprocessor network in the event of node failures, In our approach, a mesh or torus is partitioned into 4 x 4 submeshes, Subgraphs (rings and linear arrays) are mapped in each submesh and then merged to form a large ring. Using this approach, we obtain the following results in a torus. Given any f less than or equal to 2 faulty nodes, a ring which is optimal can be found in a mesh, Also, given any f less than or equal to 4 faulty nodes, a ring which is optimal can be found in a torus. Furthermore, given f less than or equal to 4 faulty nodes, a Hamiltonian cycle can be found in a torus if and only if the number of even faulty nodes is equal to the number of odd faulty nodes. Even and odd refer to the sum of the node's coordinates.