Abstract

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

Meeting Name

International Conference on Parallel and Distributed Systems, 1994

Department(s)

Computer Science

Keywords and Phrases

1-Step Recoverable Embeddings; D-Cube; Fault Tolerance; Fault Tolerant Computing; Hypercube Networks; Hypercubes; Rings

Document Type

Article - Conference proceedings

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1994 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 1994

Download

Full Text Link

Share

 
COinS