Fault-tolerant multi-destination routing in hypercube multicomputers

Multicast algorithms for faulty hypercube multicomputers are discussed. Two types of algorithms are proposed. Type I algorithms have the following features: they are distributed, in the sense that the same algorithm is implemented in all involved nodes and based on local information only; they can always find shortest paths from the source to all destinations whenever such exist; and they are easy to implement in hardware. The algorithms deal with nodes faults only, and they cannot deliver messages to those destinations that can be reached through some longer paths. Type II algorithms deal with both link faults and node faults. They can deliver messages to all reachable destinations if the total number of faults is less than the dimension of the hypercube. However, these algorithms are not easy to implement in hardware