Title :
Reliable broadcasting in hypercubes using safety levels
Author_Institution :
Dept. of Comput. Sci. & Eng., Florida Atlantic Univ., Boca Raton, FL, USA
Abstract :
We consider a distributed broadcasting algorithm for faulty hypercubes using incomplete spanning binomial trees. A faulty hypercube is a connected hypercube with faulty nodes. The incomplete spanning binomial tree proposed in this paper is a useful structure for implementing broadcasting in faulty hypercubes. It is defined as a subtree of a regular spanning binomial tree that connects all the nonfaulty nodes. The root node of such a tree is called an l-node. A method is proposed to locate a large subset of the l-node set using the concept of safety level. An optimal broadcast initiated from a safe node is proposed. When a nonfaulty source node is unsafe and there are at most n-1 faulty nodes in a faulty n-dimensional hypercube, the proposed broadcasting scheme requires at most n+1 steps. Possible extensions of the safety level concept to cover a larger subset of l-nodes are also presented
Keywords :
distributed algorithms; fault tolerant computing; hypercube networks; distributed broadcasting algorithm; faulty hypercubes; hypercubes; incomplete spanning binomial trees; reliable broadcasting; root node; safety level concept; safety levels; subtree; Broadcasting; Casting; Clocks; Computer science; Fault tolerance; Hypercubes; NP-complete problem; Reliability engineering; Safety; Synchronization;
Conference_Titel :
Fault-Tolerant Parallel and Distributed Systems, 1994., Proceedings of IEEE Workshop on
Conference_Location :
College Station, TX
Print_ISBN :
0-8186-6807-5
DOI :
10.1109/FTPDS.1994.494476