Abstract
An embedding is said to be 1-step recoverable if any single fault in the embedding can be recovered in one reconfiguration step. In this paper we present a heuristic approach to construct such 1-step recoverable embeddings. We show that to embed a k (even) length ring in ad-cube, where 6 < = k < = 3/4 2d and d < = 3, our scheme will guarantee finding a 1-step recoverable embedding, provided such an embedding exists. Compared to other previously proposed schemes, our scheme achieves much better results. A sufficient condition for the non-existence of 1-step recoverable embeddings for embedding rings of length > 3/4 2d in d-cubes is also given.
Recommended Citation
Liu, Junlin; Sager, Thomas J.; and McMillin, Bruce M., "An Improved Characterization of 1-Step Recoverable Embeddings: Rings in Hypercubes" (1992). Computer Science Technical Reports. 136.
https://scholarsmine.mst.edu/comsci_techreports/136
Department(s)
Computer Science
Keywords and Phrases
Ring, Hypercube, Embedding, Fault Tolerance, Reconfiguration.
Report Number
CSc-92-07
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1992 University of Missouri - Rolla, All rights reserved
Publication Date
24 November, 1992
Comments
The first and second Authors are Graduate Students
This work was supported In part by the National Science Foundation under Grant Number MSS-9216479, and, In part, from the Air Force Office of Scientific Research under contract number F49620-92-J-0546.