| Summary: | Abstract: "This paper proposes a fault-tolerant broadcast algorithm for injured hypercubes with a large number of faulty links by exploiting the rich connectivity of the hypercube topology. By making a simple modification to the regular Spanning Tree Broadcast (STB) algorithm, the proposed Extended STB (ESTB) algorithm can tolerate up to 2[superscript n-2] faulty links, if the hypercube is divisible, where n is the dimension of the host hypercube. Q[subscript n] is divisible if the number of faulty links in Q[subscript n] is less than or equal to 2[superscript n-2], and all the subcubes divided from Q[subscript n] are also divisible. A node N[subscript x] is called a safe node if all the links between N[subscript x] and its children nodes in the subcube are nonfaulty. Otherwise, N[subscript x] is called an unsafe node. In the ESTB algorithm, an unsafe node does not generate its children nodes but passes a message to another safe node in the same subcube to generate its children nodes. A heuristic algorithm is developed to identify the divisibility of injured hypercubes. Even though the complexity of our algorithm is exponential in its nature, our algorithm was found to identify the divisible injured hypercubes in n steps in virtually all the simulated cases. The additional depth of the spanning tree generated by the ESTB algorithm is negligible even when the number of faulty links is very large."
|
|---|