Reliable broadcast in hypercube multicomputers

Abstract

A simple algorithm for broadcasting in a hypercube multicomputer containing faulty nodes/links is proposed. The algorithm delivers multiple copies of the broadcast message through disjoint paths to all the modes in the system. Its salient feature is that the delivery of the multiple copies is transparent to the processes receiving the message and does not require the processes to know the identity of the faulty processors. The processes on nonfaulty nodes that receive the message identify the original message from the multiple copies using some scheme appropriate for the fault model used. The algorithm completes in n + 1 steps if each node can simultaneously use all of its outgoing links. If each node cannot use more than one outgoing link at a time, then the algorithm requires 2n steps.