EMBEDDING OF RINGS IN 2-D MESHES AND TORI WITH FAULTY NODES

To increase the reliability of networks embedded in meshes or tori and to allow their use in the presence of faulty nodes, efficient fault-t olerant schemes in meshes and tori are necessary, In this paper, we pr esent algorithms for embedding a ring in a mesh-type and torus-type mu ltiprocessor network in the event of node failures, In our approach, a mesh or torus is partitioned into 4 x 4 submeshes, Subgraphs (rings a nd 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 equ al 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 Hamilton ian cycle can be found in a torus if and only if the number of even fa ulty nodes is equal to the number of odd faulty nodes. Even and odd re fer to the sum of the node's coordinates.