Previous [1] [2] [3] [4] [5] [6] [7] [8] [9]


Journal of Information Science and Engineering, Vol.19 No.3, pp.467-478 (May 2003)

Local-Safety-Information-Based Fault-Tolerant
Broadcasting in Hypercubes*

Dong Xiang, Ai chen and Jie Wu+
School of Software
Tsinghua University
Beijing, 100084 P.R.C.
+Department of computer Science and Engineering
florida Atlantic University
Boca Raton, FL 33431, U.S.A.

This paper presents a method for fault-tolerant broadcasting in faulty hypercubes using a new metric called local safety. A new concept of the broadcast subcube is introduced, based on which various techniques are proposed to improve the performance of a broadcast algorithm. An unsafe hypercube can be split into a set of maximal safe subcubes. We show that if these maximal safe subcubes meet certain requirements given in the paper, broadcasting can still be carried out successfully, and in some cases optimal broadcast is still possible. The sufficient condition for optimal broadcasting is also presented. Limited backtracks are utilized in the process of broadcasting by setting up a partial broadcast tree. Extensive simulation results are presented.

Keywords: broadcasting, fault tolerance, hypercubes, local safety information, optimal solutions

Full Text () Retrieve PDF document (200305_05.pdf)

Received May 15, 2002; accepted July 25, 2002.
Communicated by Biing-Feng Wang, Stephan Olariu and Gen-Huey Chen.
*A preliminary version of the paper was presented at the 2002 International Conference on Parallel and Distributed Systems, Chungli, Taiwan.