Gossiping in the multicasting communication environment
Teofilo F. Gonzalez · 2002
The gossiping problem consists of an n processor communication network N, in which every processor has to broadcast a single message. We present an efficient algorithm to generate a communication schedule with total communication time at most n+r, where r is the radius of the network, when message multicasting is allowed. Our algorithm begins by constructing a spanning tree (or tree network T) with least possible radius. Then all the communications are carried out in the tree network as follows. Each processor waits its turn to transmit consecutively to its parent and children all the messages in its subtree. Before and after these communications, each processor must transmit to its children all the messages emanating elsewhere in the network.