New Gossip Algorithms Achieve Fast Rumor Spreading with Tiny Messages
Researchers crack the gossip bottleneck with polylog-sized messages for near-optimal speed.
Gossip algorithms are a cornerstone of distributed computing, allowing each node to contact only one neighbor per round to spread information. Prior fast rumor spreading methods required messages of size linear in the network size (n), undermining gossip's key advantage of low per-node overhead. A new paper from Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan (accepted at PODC 2026) answers a fundamental question: Can fast rumor spreading be done with small messages?
Their answer is yes. They introduce two algorithms that use only polylog(n)-sized messages. The first algorithm achieves O(c log n / Φ_c) rounds for any c ≥ 1, where Φ_c is the weak conductance—this bound is essentially optimal. The second algorithm runs in Õ(D + √n) rounds (D = network diameter) with high probability, independent of conductance, and can be modified to output a minimum spanning tree in the same number of rounds (also round-optimal, even for non-gossip algorithms). The key innovation is a novel use of graph sketches to overcome communication bottlenecks while keeping messages small. This makes gossip practical for large-scale, unknown networks without sacrificing speed.
- First algorithm achieves O(c log n / Φ_c) rounds with polylog(n) messages, optimal in weak conductance.
- Second algorithm runs in Õ(D + √n) rounds independent of conductance, also yielding an optimal MST.
- Uses graph sketches (Ahn, Guha, McGregor, SODA 2012) to compress information and avoid linear-sized messages.
Why It Matters
Makes gossip-based protocols viable for massive networks without overwhelming bandwidth or node memory.