FAST GOSSIPING BY SHORT MESSAGES

Gossiping is the process of information diffusion in which each node o f a network holds a packet that must be communicated to all other node s in the network. We consider the problem of gossiping in communicatio n networks under the restriction that communicating nodes can exchange up to a fixed number p of packets at each round. In the first part of the paper we study the extremal case p = 1 and we exactly determine t he optimal number of communication rounds to perform gossiping for sev eral classes of graphs, including Hamiltonian graphs and complete k-ar y trees. For arbitrary graphs we give asymptotically matching upper an d lower bounds. We also study the case of arbitrary p and we exactly d etermine the optimal number of communication rounds to perform gossipi ng under this hypothesis for complete graphs, hypercubes, rings, and p aths. Finally, we investigate the problem of determining sparse networ ks in which gossiping can be performed in the minimum possible number of rounds.