Title :
Optimal ring embedding in hypercubes with faulty links
Author :
Latifi, S. ; Zheng, S.-Q. ; Bagherzadeh, N.
Author_Institution :
Dept. of Electr. & Comput. Eng., Nevada Univ., Las Vegas, NV, USA
Abstract :
The authors show that in an n-dimensional hypercube (Q/sub n/), up to n-2 links can fail before destroying all available Hamiltonian cycles. They present an efficient algorithm which identifies a characterization of a Hamiltonian cycle in Q/sub n/, with as many as n-2 faulty links, in O(n/sup 2/) time. Generating a fault-free Hamiltonian cycle from this characterization can be easily done in linear time. An important application of this work is in optimal simulation of ring-based multiprocessors or multicomputer systems by hypercubes. Compared with the existing fault-tolerant embeddings based on link-disjoint Hamiltonian cycles, the algorithm specifies such a cycle that tolerates twice as many faulty links.<>
Keywords :
digital simulation; fault tolerant computing; hypercube networks; Hamiltonian cycles; fault-tolerant embeddings; faulty links; hypercubes; linear time; multicomputer systems; optimal ring embedding; optimal simulation; ring-based multiprocessors; Character generation; Computer science; Fault diagnosis; Fault tolerance; Hypercubes; Network topology;
Conference_Titel :
Fault-Tolerant Computing, 1992. FTCS-22. Digest of Papers., Twenty-Second International Symposium on
Conference_Location :
Boston, MA, USA
Print_ISBN :
0-8186-2875-8
DOI :
10.1109/FTCS.1992.243602
