An embedding is 1-step recoverable if any single fault occurs, the embedding can be reconfigured in one reconfiguration step to maintain the structure of the embedded graph. In this paper we present an efficient scheme to construct this type of 1-step recoverable ring embeddings in the hypercube. Our scheme will guarantee finding a 1-step recoverable embedding of a length-k (even) ring in a d-cube where 6 less than or equal to k less than or equal to (3/4)2/sup d/ and d greater than or equal to 3, provided such an embedding exists. Unlike previously proposed schemes, we solve the general problem of embedding rings of different lengths and the resulting embeddings are of smaller expansion than in previous proposals. A sufficient condition for the non-existence of 1-step recoverable embeddings of rings of length >(3/4)2d in d-cubes is also given
Jun-Lin Liu et al., "An Improved Characterization of 1-Step Recoverable Embeddings: Rings in Hypercubes," Proceedings of the International Conference on Parallel and Distributed Systems, 1994, Institute of Electrical and Electronics Engineers (IEEE), Jan 1994.
The definitive version is available at http://dx.doi.org/10.1109/ICPADS.1994.590363
International Conference on Parallel and Distributed Systems, 1994
Keywords and Phrases
1-Step Recoverable Embeddings; D-Cube; Fault Tolerance; Fault Tolerant Computing; Hypercube Networks; Hypercubes; Rings
Article - Conference proceedings
© 1994 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.