Broadcast and gossip in line-communication mode

AbstractThis paper addresses the problem of efficiently performing two important operations of communication in networks, namely broadcast and gossip. We study these operations in the line-communication model that is similar to the circuit-switching technique. We propose a simpler proof of the fundamental result, due to A. Farley, that gives the exact broadcast time, ⌜log2 n⌝ steps, in any connected network of order n. In the second part we construct gossip algorithms in any tree network and we prove that they are optimal or asymptotically optimal. We finally give a precise idea of the shape of trees in which gossip is possible in ⌜log2 n⌝ steps. Finally, we present general results on gossip in any connected graph