Abstract
The problem of tolerating faulty nodes in hypercubes has been studied by many researchers either by using spares or by reconfiguration. In this paper, an algorithm for tolerating faulty nodes in hypercubes is presented. The algorithm is based on using general spanning trees for reconfiguring the hypercube to avoid faulty nodes. The algorithm contains two phases: the first phase involves the construction of the spanning tree, and the second one is for reconfiguring the hypercube should a faulty node be detected. The reconfiguration process introduced consists of two basic steps. First, the faulty node is disconnected from the spanning tree. Then, a new spanning tree is constructed by reconnecting the children of the faulty node to the spanning tree. This paper deals with reconfiguring faulty hypercubes; however, the same algorithm can be generalized to work for reconfiguration of multicomputer networks in general in the presence of faults. Single fault coverage of 100% and almost 100% fault coverage of double and triple faults are achieved by the proposed algorithm, with no extra-dilation for hypercubes having a dimension of n≥ 10. Simulation results for the algorithm under more than three faults also are presented. Fault coverage and congestion results for up to 60 faults having different cube sizes are discussed.
Research supported in part by NSF and by the Texas Advanced Technology Program under grant no. 999903-029.
This author is supported by King Fahd Univ. of Petroleum and Minerals, Saudi Arabia, Dhahran 31261
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Altawil, D. Avresky, and D. Pradhan, “Fault Tolerance of Hypercubes Using Spanning Trees,” Technical Report 93-055, Department of Computer Science, Texas A & M University, Dec. 93.
K.M. Altawil and D.R. Avresky, “Reconfiguration of Spanning Trees in Faulty Hypercubes,” Proc. 23rd Int'l Con. on Par. Proc., Chicago, Illinois, USA, Aug. 1994.
D.R. Avresky et al., “An Approach to Fault Diagnosis in Multimicrocomputer Systems: Algorithm and Simulation,” Proc. 17th Int'l Symp. on Fault Tolerant Computing, pp. 305–310, June 1987.
S.G. Aki, The Design and Analysis of Parallel Algorithms. Prentice-Hall International, Inc., 1989.
A. Bagchi and S. Hakimi, “Data Transfers in Broadcast Networks,” IEEE Trans. on Comp., Vol. C-41, No. 7, July 1992, pp. 842–847.
P. Banerjee, “Strategies for Reconfiguring Hypercubes Under Faults,” Proc. 20th Int'l Symp. on Fault Tolerant Computing. pp. 210–217, June 1990.
J. L. Bentley, “A Parallel Algorithm for Constructing Minimum Spanning Trees,” J. of Algorithms, Vol. 1, No. 1, pp. 51–59, March 1980.
A. Bagchi, S. Hakimi, J. Mitchem, and E. Schmeichel, “Parallel Algorithms For Gossiping by Mail,” Information Processing Letters, Vol. 34, pp. 197–202, April 1990.
D. Bertsekas, C. Ozveren, G. Stamoulis, P. Tseng, and J. Tsitsiklis, “Optimal Communication Algorithms for Hypercubes,” J. of Par. and Dist. Computing, Vol 11, pp. 263–275, 1991.
T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. McGraw-Hill, pp. 498–513, 1990.
M. Y. Chen and S. Lee, “Fault-Tolerant Embedding of Complete Binary Trees in Hypercubes,” IEEE Tran. on Par. and Dist. Sys., Vol. 4, No. 3, March 1993.
S. Chau and A. Liestman, “A Proposal for a Fault Tolerant Binary Hypercube Architecture,” Proc. 19th Int'l Symp. on Fault Tolerant Computing, pp. 323–330, June 1989.
S. Dutt and J. Hayes, “An Automorphic Approach to the design of Fault-Tolerant Multiprocessors,” Proc. 19th Int'l Symp. on Fault Tolerant Computing, pp. 496–503, June 1989.
Kemal Efe and Kumar Ramaiyer, “Congestion and Fault Tolerance of Binary Tree Embeddings on Hypercube,” Fifth Int'l. Par. Proc. Symp., 1991.
G. Frederickson, “Data Structures for On-Line Updating of Minimum Spanning Trees with Applications,” SIAM J. Comput, Vol 14, No 4, Nov. 1985.
R. Gallager, P. Humblet, and P. Spira, “A Distributed Algorithm for Minimum Weight Spanning Trees,” ACM Trans. on Prog. Languages and Systems. Vol. 5, No. 1, pp. 66–77, Jan. 1983.
S. Johnsson, and C. Ho, “Optimum Broadcasting and Personalized Communication in Hypercubes,” IEEE Trans. on Comp., Vol. C-38, No. 9, pp. 197–202, Sept. 1989.
S. Kwan and W Ruzzo. “Adaptive Parallel Algorithms for Finding Minimum Spanning Trees,” Proc, of the 1984 Int'l. Conf. on Parallel Processing, Bellaire, Michigan, pp. 439–443, Aug. 1984.
T. Lee and J. Hayes, “Design of Gracefully Degradable Hypercube-Connected Systems,” J. of Parallel and Distributed Computing, Vol. 14, pp. 390–401, 1992.
M. Peercy and P. Banerjee, “Distributed Algorithms for Shortest-Path, Deadlock-Free Routing and Broadcasting in Arbitrarily Faulty Hypercubes,” Proc. 20th Int'l Symp. on Fault Tolerant Computing, pp. 218–225, June 1990.
S. Ravindran and A. Gibbons, “Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube,” Information Processing Letters. Vol. 45, pp. 321–325, April 1993.
D. Rennets, “On Implementing Fault Tolerance in Binary Hypercubes,” Proc. 16th Int'l Symp. on Fault Tolerant Computing, pp. 344–349, June 1986.
K. Ravindran, G. Sing, and P. Gupta, “Reconfiguration of Spanning Trees in Networks in the Presence of Node Failures,” The 13th Int'l. Conf. on Distr. Comp. Sys., pp. 219–226. May 1993.
C. Raghavendra, P. Yang, and S. Tien, “Free Dimensions — An Effective Approach to Achieving Fault Tolerance in Hypercubes,” Proc. 22nd Int'l Symp. on Fault Tolerant Computing, pp. 170–177, July 1992.
Y. Saad and M. Schultz, “Topological Properties of Hypercubes,” IEEE Tran. on Comp., Vol. C-37, No. 7, July 1988. pp. 867–872.
A. Sen, A. Sengupta, and S. Bandyopadhyay, “On Some Topological Properties of Hypercube, Incomplete Hypercube and Supercube,” Seventh Int'l. Par. Proc. Symp., 1993.
G. Stamoulis and J. Tsitsiklis, “An Efficient Algorithm for Multiple Simultaneous Broadcasts in the Hypercube,” Information Processing Letters, Vol. 46, pp. 219–224. July 1993.
G. Stamoulis and J. Tsitsiklis, “Efficient Routing Schemes for Multiple Broadcasts in Hypercubes,” IEEE Trans. on Par. and Dist. Sys., Vol. 4, No. 7, pp. 725–739, July 1993.
A. Wagner, “Embedding All Binary Trees in the Hypercube,” J. of Par. and Dist. Computing, Vol. 18, pp. 33–43, 1993.
F. Wang and F. Lin, “On Constructing Multiple Spanning Trees in a Hypercube,” Information Processing Letters, Vol. 45, pp. 177–183, March 1993.
W.W. White, “Mapping General Trees and Graphs into the Hypercube,” Proc. of the ISCA Int'l. Conf., Parallel and Distributed Computing, pp. 157–161, October 14–16. 1993.
P. Yang and C. Raghavendra, “Embedding and Reconfiguration of Binary Trees in Faulty Hypercubes,” Sixth Int'l. Par. Proc. Symp., pp. 2–9, 1992.
P. Yang and C. Raghavendra, “Reconfiguration of Binary Trees in Faulty Hypercubes,” Seventh Int'l. Par. Proc. Symp., pp. 401–405, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avresky, D.R., Al-Tawil, K.M. (1994). Reconfiguration of faulty hypercubes. In: Echtle, K., Hammer, D., Powell, D. (eds) Dependable Computing — EDCC-1. EDCC 1994. Lecture Notes in Computer Science, vol 852. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58426-9_156
Download citation
DOI: https://doi.org/10.1007/3-540-58426-9_156
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58426-1
Online ISBN: 978-3-540-48785-2
eBook Packages: Springer Book Archive