Fault-tolerant embeddings of rings, meshes, and tori in hypercubes
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors study the ability of the hypercube to implement algorithms with ring, mesh, and torus communication patterns when the hypercube contains faults. The 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 (n-h(n)) odd faulty nodes, where h(n) is a function such that h(n)=O( square root n log n). Given the above bounds on the parities of the faults, the result obtained improved upon previous results both in the number of faults that are tolerated and in the length of the ring that is embedded. In addition, the result leads to improved bounds for fault-free embeddings of meshes and tori into faulty hypercubes.Keywords
This publication has 10 references indexed in Scilit:
- Asymptotically tight bounds for computing with faulty arrays of processorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Coding theory, hypercube embeddings, and fault tolerancePublished by Association for Computing Machinery (ACM) ,1991
- Efficient robust parallel computationsPublished by Association for Computing Machinery (ACM) ,1990
- Running algorithms efficiently on faulty hypercubesPublished by Association for Computing Machinery (ACM) ,1990
- Expanders might be practical: fast algorithms for routing around faults on multibutterfliesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Topological properties of hypercubesIEEE Transactions on Computers, 1988
- How robust is the n-cube?Information and Computation, 1988
- A new look at fault-tolerant network routingInformation and Computation, 1987
- Reconfiguring a hypercube in the presence of faultsPublished by Association for Computing Machinery (ACM) ,1987
- $B$-valuations of graphsCzechoslovak Mathematical Journal, 1972