Gossiping in Minimal Time
David W. Krumme, George V. Cybenko, Kavita Venkataraman · SIAM Journal on Computing · 1992
The gossip problem involves communicating a unique item from each node in a graph to every other node. This paper studies the minimum time required to do this under the weakest model of parallel communication, which allows each node to participate in just one communication at a time as either sender or receiver. A number of topologies are studied, including the omplete graph, grids, hypercubes, and rings. Definitive new optimal time algorithms are derived for complete graphs, rings, regular grids, and toroidal grids that significantly extend existing results. In particular, an open problem about minimum time gossiping in complete graphs is settled. Specifically, for a graph with N nodes, at least $\log _\rho N$ communication steps, where the logarithm is in the base of the golden ratio $\rho $, are required by any algorithm under the weakest model of communication. This bound, which is approximately $1.44\log _2 N$, can be realized for some networks and so the result is optimal.