Successive Broadcasts on Hypercube

Broadcasting is an information dissemination problem in which information originating at one node of a communication network must be transmitted to all the other nodes as quickly as possible [FLar, HHL86]. In this paper, we consider the problem in which all the nodes of a network must, by turns, broadcast a distinct message. We call this problem the successive broadcasts problem. Successive broadcasts is a communication pattern that appears in several parallel implementations of linear algebra algorithms on distributed memory multicomputers. Note that the successive broadcasts problem is different from the gossip problem [HHL86] in which all the nodes must perform a broadcast in any order, even simultaneously. We present an algorithm solving the successive broadcasts problem on hypercubes. We derive a lower bound on the time of any successive broadcasts algorithms that shows that our algorithm is within a factor of 2 of the optimality. Key words: Broadcasting, hypercube, successive bro..