Fast Gossip-Based Rumor Spreading Using Small Messages

We study gossip algorithms for the fundamental rumor spreading problem, where the goal is to disseminate a rumor from a given source node to all nodes in an arbitrary (and unknown) graph. Gossip algorithms allow each node to call only one neighbor per round and are therefore highly message-efficient, with low per-node communication overhead per round. The state of the art works present fast gossip algorithms, however they typically leverage large-sized messages. This undermines the lightweight communication advantage of gossip, since even though only one neighbor is contacted per round, the message size can be linear in í µí±, the network size. Hence, a fundamental question is whether one can perform fast gossip using small messages. The main contribution of this paper is to answer the above question in the affirmative and present two gossip algorithms that achieve fast rumor spreading using messages of polylog 𝑛 size. Specifically , we show the following results: (1) We present a gossip algorithm for rumor spreading that runs in 𝑂(𝑐 log𝑛/Φ𝑐 ) rounds for every 𝑐 ⩾ 1, and Φ𝑐 is the weak conductance. Our algorithm's run time not only improves over the Censor-Hillel-Shachnai bound [SODA 2011; SICOMP 2012], but more significantly, it uses messages of small (polylog 𝑛) size, unlike the prior work that used messages of large (at least linear in 𝑛) size. Our bound in terms of weak conductance is essentially optimal. (2) We also present a gossip algorithm for rumor spreading that depends on the network diameter (and is independent of the graph's conductance), which runs in 𝑂̃(𝐷 +√𝑛) rounds with high probability and uses small (polylog 𝑛 size) messages. Our bound is a significant improvement over the gossip algorithm of 𝑂̃(√𝑛𝐷) due to Ghaffari and Kuhn [DISC 2018], which also uses small-sized messages. We note that our algorithm (unlike that of Ghaffari and Kuhn) is optimal for when 𝐷 = Ω(√𝑛). Furthermore, our gossip algorithm can be modified to output a minimum spanning tree (MST) in the same number of rounds, which is essentially round-optimal (even for non-gossip algorithms). Our gossip algorithms use graph sketches [Ahn, Guha, McGregor, SODA 2012] in a novel way to overcome communication bottlenecks and achieve small communication overhead with small message sizes.