About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SPDP 1992
Conference paper
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.