Fault-tolerant embeddings of rings, meshes, and tori in hypercubes

Abstract

This paper studies the ability of the hypercube to implement algorithms with ring, mesh, and torus communication patterns when the hypercube contains faults. Our primary result is a fault-free embedding of the longest possible ring into an n-cube with at most (n - h(n)) even faulty nodes and (ra - h(n)) odd faulty nodes, where h(n) is a function such that h(n) = O ( Vnlogn ) . Given the above bounds on the parities of the faults, our result improves upon previous results both in the number of faults that are tolerated and in the length of the ring that is embedded. In addition, our result leads to improved bounds for fault-free embeddings of meshes and tori into faulty hypercubes.