Safety levels-an efficient mechanism for achieving reliable broadcasting in hypercubes

We consider a distributed broadcasting algorithm for injured hypercubes using incomplete spanning binomial trees. An injured 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 injured hypercubes. It is defined as a sub-tree of a regular spanning binomial tree that connects all the nonfaulty nodes. We show that in an injured n-dimensional hypercube with m faulty nodes, there are at least 2ⁿ-2^m source nodes (called l-nodes), each of which can generate an incomplete spanning binomial tree. A method is proposed to locate a large subset of the l-node set using the concept of safety level. The safety level of each node in an n-dimensional hypercube can be easily calculated through n-1 rounds of information exchange among neighboring nodes. 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 an injured n-dimensional hypercube, the proposed broadcasting scheme requires at most n+1 steps