How to Spread a Rumor: Call Your Neighbors or Take a Walk?

George Giakkoupis, Frederik Mallmann-Trenn, Hayk Saribekyan

Researchers from INRIA, King’s College London, and the University of Cambridge recently explored a fundamental question in distributed computing: What is the most efficient way to spread a piece of information (a "rumor") across a network?

Traditionally, node-based protocols like PUSH-PULL are used, where computers "call" their neighbors to swap data. This research investigates an alternative: mobile agents—software entities or physical robots—that wander the network via random walks to deliver the news. This paper provides the first systematic comparison between these traditional rumor-spreading protocols and agent-based alternatives.

Protocol Definitions

The study analyzes four specific protocols to understand the trade-offs between node-based and agent-based dissemination:

  1. PUSH: Informed nodes pick a random neighbor to send information to.
  2. PUSH-PULL: Nodes call neighbors; if either has the information, they both receive it.
  3. VISIT-EXCHANGE: Both nodes and agents store information. When an agent visits a node, they swap all known data.
  4. MEET-EXCHANGE: Only agents store information. They only swap data when two agents land on the same node simultaneously.

Synthetic Graph Families

As a theoretical study, the authors evaluate their claims using synthetic graph families designed to highlight specific edge cases where protocols diverge in performance.

Figure 1: Synthetic graph families used for evaluation: (a) Star, (b) Double-Star, (c) Heavy Binary Tree, (d) Double Heavy Binary Tree, and (e) Cycle-of-Stars-of-Cliques.
  • Star and Double-Star Graphs (a, b): These illustrate scenarios where PUSH-PULL fails due to bottlenecks (like a single bridge) that agents easily bypass.
  • Heavy Binary Trees (c, d): These show where agents can get "lost" in high-volume areas (leaves), allowing node-based PUSH to outperform them.
  • Cycle-of-Stars-of-Cliques (e): A complex regular graph used to demonstrate a logarithmic performance gap between VISIT and MEET protocols.

Key Insights

The Power of Fairness

Agent-based protocols are "locally fair" because random walks from a stationary distribution traverse every edge with the same frequency. In a "Double Star" graph (two stars connected by a single bridge), PUSH-PULL is slow because nodes rarely "call" the bridge. Agents, however, cross the bridge much more reliably, leading to an exponential speedup ($O(\log n)$ vs $\Omega(n)$).

Asymptotic Equivalence

A core theoretical contribution is the proof that on any $d$-regular graph (where every node has the same number of neighbors) with $d = \Omega(\log n)$, PUSH and VISIT-EXCHANGE have the same asymptotic broadcast time. This suggests that at a certain level of network density and symmetry, the specific mechanism of movement (calling vs. walking) becomes secondary to the network structure itself.

Nodes as Mailboxes

The paper highlights that VISIT-EXCHANGE is generally superior to MEET-EXCHANGE. In VISIT, the nodes act as persistent "mailboxes," allowing information to persist even after an agent leaves. In MEET, information only spreads during fleeting agent-to-agent encounters, which is significantly harder to achieve and results in slower dissemination.

Results and Future Directions

The authors prove that in general (non-regular) graphs, no protocol is strictly superior. They provide specific examples where PUSH is polynomially faster than agents, and vice versa.

Key results include:

  • Regular Graph Performance: On regular graphs with at least logarithmic degree, PUSH and VISIT-EXCHANGE are asymptotically identical in speed.
  • Protocol Incomparability: In non-regular graphs, protocol performance is highly dependent on topology.
  • MEET-EXCHANGE Lag: MEET-EXCHANGE is asymptotically at least as slow as VISIT-EXCHANGE on all regular graphs.

Future work remains to explore "sparse" regular graphs with sub-logarithmic degrees, scenarios with a sparse number of agents ($|A| \ll n$), and the robustness of agent-based models to node or link failures.

Summary updated

BibTeX
@inproceedings{giakkoupis2019how,
  author = {George Giakkoupis and Frederik Mallmann-Trenn and Hayk Saribekyan},
  title = {{How to Spread a Rumor: Call Your Neighbors or Take a Walk?}},
  booktitle = {PODC},
  year = {2019},
  doi = {10.1145/3293611.3331622},
}
Figure