Fault-tolerant multicast with traffic-balancing in hypercubes

Multicast is an important interprocessor communication pattern existing in various parallel application algorithms. This paper proposes a new multicast algorithm for hypercube computers that not only minimizes the number of hops required for delivery of the message and keeps a least possible amount of traffic, but also takes into consideration of balancing traffic among the active processors to maximize the parallelism in communication. Our algorithm has a time complexity of O(nN) for fault-tolerant multicasting in a hypercube of N=2ⁿ processors containing an arbitrary number of faulty processors