Broadcast and gossip in line-communication mode (Q1382273)

In a line-communication network, two nodes can communicate directly via a path in a single time step and different pairs of nodes can do so provided edge-disjoint paths are used. In the broadcast problem one node has a piece of information which is to be transmitted to all nodes; in the gossip problem each node has a distinct piece of information and all such pieces are to be transmitted to all nodes. The paper gives a simple proof of Farley's result that the broadcast time is \(\lceil \log_2 n\rceil\) steps in a connected network with \(n\) nodes. For the gossip problem upper and lower bounds are given for the gossip time for connected graphs and for trees. Gossip algorithms are constructed for trees and are shown to be optimal or asymptotically optimal. Also trees are constructed in which gossip is possible in \(\lceil \log_2n \rceil\) steps.