pith. sign in

arxiv: 2605.14376 · v1 · pith:T4QV4ENInew · submitted 2026-05-14 · 💻 cs.DC · cs.DS

Fast Gossip-based Rumor Spreading using Small Messages

Fabien Dufoulon , William K. Moses Jr. , Gopal Pandurangan This is my paper

Pith reviewed 2026-06-30 20:36 UTC · model grok-4.3

classification 💻 cs.DC cs.DS
keywords gossip algorithmsrumor spreadinggraph sketchesdistributed algorithmsarbitrary graphsweak conductanceminimum spanning treesmall messages
0
0 comments X

The pith

Gossip algorithms can spread a rumor throughout an arbitrary unknown graph in near-optimal time using messages no larger than polylog n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper demonstrates that fast rumor spreading remains possible in the gossip model even when messages must stay small. It gives one algorithm whose running time depends on the graph's weak conductance and matches known lower bounds, and a second whose time depends only on the diameter and square root of the number of nodes. Both results hold with high probability and extend to computing a minimum spanning tree. This matters because gossip protocols contact only one neighbor per round; keeping messages small preserves their efficiency advantage over flooding methods that use large messages.

Core claim

The authors show that two new gossip algorithms suffice for fast rumor spreading with polylog n message size. The first runs in O(c log n / Φ_c) rounds for any c and is optimal with respect to weak conductance. The second runs in Õ(D + √n) rounds independent of conductance and can also produce a minimum spanning tree, which is essentially optimal even without the gossip restriction. Graph sketches are used in a novel way to overcome communication bottlenecks that would otherwise force larger messages.

What carries the argument

graph sketches integrated into the gossip protocol to handle information aggregation without enlarging individual messages beyond polylog n size

If this is right

  • The conductance-based algorithm is essentially optimal for every c ≥ 1.
  • The diameter-based algorithm works even in graphs with poor conductance.
  • Both algorithms succeed with high probability in any unknown graph.
  • The same round bound yields a minimum spanning tree as output.
  • The approach keeps per-round communication to one neighbor with small payload.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method could apply to other distributed tasks that benefit from small messages, such as aggregation or leader election.
  • Further refinements of the sketch technique might reduce the polylog factor or adapt to dynamic graphs.
  • The MST construction opens a path to building low-overhead spanning structures in the same lightweight model.
  • Practical networks with bandwidth limits might now run rumor spreading without the previous speed penalty.

Load-bearing premise

Graph sketches can be combined with gossip calls in a way that keeps every transmitted message at polylog n size while still achieving the stated round counts.

What would settle it

A specific graph family where any gossip protocol that keeps messages at polylog n size requires more than O~(D + √n) rounds or more than O(log n / Φ) rounds to spread the rumor.

Figures

Figures reproduced from arXiv: 2605.14376 by Fabien Dufoulon, Gopal Pandurangan, William K. Moses Jr..

Figure 1
Figure 1. Figure 1: A 𝑐-barbell of 𝑛 nodes. There are 𝑐 cliques, each containing 𝑛/𝑐 nodes, connected in a path. The above definition implies that any graph 𝐺 with weak conductance Φ𝑐 , for some value of the parameter 𝑐 ⩾ 1, satisfies the following (structural) property. For each node 𝑣, there exists some maximal connected component that contains 𝑣, of size at least 𝑛/𝑐, and with conductance at least Φ𝑐 . (Here, maximal is me… view at source ↗
read the original abstract

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 present fast gossip algorithms, however they typically leverage large-sized messages. This undermines the light-weight communication advantage of gossip, since even though only one neighbor is contacted per round, the message size can be linear in $n$, 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{n} size. Specifically, we present the following algorithms: 1. An algorithm that runs in $O(c \log n / \Phi_c)$ rounds for every $c \geq 1$, and $\Phi_c$ is the weak conductance. Our bound in terms of weak conductance is essentially optimal. 2. An algorithm that depends on the network diameter (and is independent of the graph's conductance), which runs in $\tilde{O}(D+\sqrt{n})$ rounds with high probability. Our 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper studies gossip-based rumor spreading in arbitrary unknown graphs under the constraint that each node contacts only one neighbor per round. It claims to affirmatively answer whether fast spreading is possible with polylog n sized messages by presenting two algorithms: (1) one running in O(c log n / Φ_c) rounds for any c ≥ 1, where Φ_c denotes weak conductance (claimed essentially optimal), and (2) one running in Õ(D + √n) rounds w.h.p. that can additionally output an MST (claimed round-optimal even outside the gossip model). Both rely on a novel integration of linear graph sketches from Ahn et al. (SODA 2012) to overcome communication bottlenecks while preserving small message sizes.

Significance. If the central claims hold, the work would be a notable contribution to distributed computing by showing that the message-efficiency advantage of the gossip model can be retained while matching or approaching the best-known round complexities previously achieved only with large (linear-sized) messages. The conductance-based bound is presented as tight, and the diameter-based algorithm's ability to also produce an MST adds value. Credit is due for attempting to reduce the sketch operations to the strict one-call-per-round model without inflating payloads.

major comments (3)
  1. [§3] §3 (Conductance-based algorithm): The central claim that sketch merging and updates from Ahn et al. can be serialized into single neighbor calls per round while keeping effective message size polylog n and preserving the O(c log n / Φ_c) high-probability bound is load-bearing but lacks an explicit bit-complexity calculation or error-accumulation argument for repeated merges under the one-call constraint in unknown graphs.
  2. [§4.2] §4.2 (Diameter-based algorithm, sketch propagation): The local neighbor-selection rule for maintaining and exchanging sketches to achieve Õ(D + √n) rounds is not shown to guarantee rumor propagation without hidden extra rounds or payload growth; this directly affects whether the stated bound holds in arbitrary graphs.
  3. [Theorem 2] Theorem 2 (MST construction): The claim that the same Õ(D + √n) round bound yields an MST is load-bearing for the second contribution, yet the reduction from rumor spreading to MST output via sketches does not address how the one-call model affects the connectivity queries needed for the MST.
minor comments (2)
  1. [Preliminaries] The definition of weak conductance Φ_c is used in the main theorems but appears only informally in the introduction; a formal definition should be added to the preliminaries.
  2. [Figure 2] Figure 2 (sketch merging illustration) does not label the per-message bit sizes, making it hard to verify the polylog n claim visually.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments. We address each major point below and will revise the manuscript to incorporate additional technical details, calculations, and proofs as requested. These additions clarify the arguments without changing the algorithms or asymptotic bounds.

read point-by-point responses

  1. Referee: [§3] §3 (Conductance-based algorithm): The central claim that sketch merging and updates from Ahn et al. can be serialized into single neighbor calls per round while keeping effective message size polylog n and preserving the O(c log n / Φ_c) high-probability bound is load-bearing but lacks an explicit bit-complexity calculation or error-accumulation argument for repeated merges under the one-call constraint in unknown graphs.

    Authors: We agree an explicit bit-complexity analysis and error bound would strengthen the section. In revision we will add a new subsection (or appendix) that (i) details the serialization: each linear sketch is partitioned into O(log n) words and merged sequentially over consecutive rounds while respecting the single-neighbor call, (ii) shows the per-message size remains O(log² n) bits because only one sketch component is transmitted per call, and (iii) bounds error accumulation via the union bound over O(log n) merges per edge together with the O(1/Φ_c) round horizon; the failure probability stays 1/poly(n). The extra serialization rounds are absorbed into the existing O(log n) factor, preserving the stated round bound. revision: yes

  2. Referee: [§4.2] §4.2 (Diameter-based algorithm, sketch propagation): The local neighbor-selection rule for maintaining and exchanging sketches to achieve Õ(D + √n) rounds is not shown to guarantee rumor propagation without hidden extra rounds or payload growth; this directly affects whether the stated bound holds in arbitrary graphs.

    Authors: We will expand §4.2 with a formal lemma proving that the local selection rule (based on sketch difference norms) produces a virtual overlay whose diameter is O(D + √n) and that each sketch exchange occurs in a single call without payload inflation beyond polylog n. The proof shows that propagation follows a breadth-first layering that respects the one-call constraint; no auxiliary rounds are introduced because the selection is computed locally from already-received sketch fragments. We will also include a short calculation confirming that the total communication per node remains O(√n log² n) bits. revision: yes

  3. Referee: [Theorem 2] Theorem 2 (MST construction): The claim that the same Õ(D + √n) round bound yields an MST is load-bearing for the second contribution, yet the reduction from rumor spreading to MST output via sketches does not address how the one-call model affects the connectivity queries needed for the MST.

    Authors: We will augment the proof of Theorem 2 to explicitly integrate the connectivity queries of the sketch-based MST algorithm (a distributed variant of Borůvka) into the same sketch-exchange schedule used for rumor spreading. Each connectivity query is answered by a constant number of sketch merges that are serialized exactly as in the diameter-based rumor-spreading phase; the one-call constraint is maintained by pipelining the queries along the same neighbor-selection rule. The round overhead remains within the Õ(D + √n) bound because the number of Borůvka phases is O(log n) and each phase reuses the existing propagation infrastructure. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithms constructed from external graph-sketch primitives

full rationale

The paper claims two new gossip algorithms achieving the stated round bounds with polylog n messages by using graph sketches from Ahn et al. (SODA 2012) 'in a novel way'. No self-definitional steps appear, no parameters are fitted to data and then relabeled as predictions, and the cited sketch work is external (different authors). The derivation consists of algorithmic constructions that integrate an independent primitive into the single-call gossip model; the central claims do not reduce to the paper's own inputs by construction. This is the common case of a self-contained algorithmic result built on prior independent results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper builds on existing graph sketches from Ahn et al. without introducing new free parameters or entities; relies on standard distributed computing model assumptions.

axioms (1)
  • domain assumption Standard synchronous gossip model where each node contacts exactly one neighbor per round in an arbitrary unknown graph.
    Invoked in the problem definition and algorithm descriptions in the abstract.

pith-pipeline@v0.9.1-grok · 5849 in / 1220 out tokens · 31493 ms · 2026-06-30T20:36:26.615497+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 9 canonical work pages

  1. [1]

    Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Analyzing graph structure via linear measurements. InProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 459–467

    2012

  2. [2]

    Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, and Petar Maymounkov. 2012. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. InProceedings of the forty-fourth annual ACM symposium on Theory of computing. 961–970

    2012

  3. [3]

    Kelner, and Petar Maymounkov

    Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. 2017. Rumor Spreading with No Dependence on Conductance. SIAM J. Comput.46, 1 (2017), 58–79. doi:10.1137/14099992X

    work page doi:10.1137/14099992x 2017

  4. [4]

    Keren Censor-Hillel and Hadas Shachnai. 2011. Fast Information Spreading in Graphs with Large Weak Conductance. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440–448

    2011

  5. [5]

    Keren Censor-Hillel and Hadas Shachnai. 2012. Fast Information Spreading in Graphs with Large Weak Conductance.SIAM J. Comput.41, 6 (2012), 1451–1465. doi:10.1137/110845380

    work page doi:10.1137/110845380 2012

  6. [6]

    Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, and Alessandro Panconesi. 2018. Rumor spreading and conductance.Journal of the ACM (JACM)65, 4 (2018), 1–21

    2018

  7. [7]

    Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Almost tight bounds for rumour spreading with conductance. InProceedings of the forty-second ACM symposium on Theory of computing. 399–408

    2010

  8. [8]

    Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Rumour spreading and graph conductance. InProceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1657–1663

    2010

  9. [9]

    Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2011. Rumor spreading in social networks.Theoretical Computer Science412, 24 (2011), 2602–2610

    2011

  10. [10]

    Robert Elsässer. 2006. On the communication complexity of randomized broadcasting in random-like graphs. InProceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures. 148–157

    2006

  11. [11]

    Paul Erdös and Richard Rado. 1960. Intersection Theorems for Systems of Sets.Journal of the London Mathematical Societys1-35, 1 (1960), 85–90. doi:10.1112/jlms/s1-35.1.85

    work page doi:10.1112/jlms/s1-35.1.85 1960

  12. [12]

    Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. 1990. Randomized broadcast in networks.Random Structures & Algorithms1, 4 (1990), 447–460

    1990

  13. [13]

    Frieze and Geoffrey R

    Alan M. Frieze and Geoffrey R. Grimmett. 1985. The shortest-path problem for graphs with random arc-lengths.Discrete Applied Mathematics10, 1 (1985), 57–77

    1985

  14. [14]

    Mohsen Ghaffari and Fabian Kuhn. 2018. Distributed MST and broadcast with fewer messages, and faster gossiping. In32nd International Symposium on Distributed Computing (DISC 2018), Vol. 121. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 30–1

    2018

  15. [15]

    George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). 57–68

    2011

  16. [16]

    George Giakkoupis, Frederik Mallmann-Trenn, and Hayk Saribekyan. 2019. How to Spread a Rumor: Call Your Neighbors or Take a Walk?. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, Peter Robinson and Faith Ellen (Eds.). ACM, 24–33. doi:10.1145/3293611.3331622

    work page doi:10.1145/3293611.3331622 2019

  17. [17]

    George Giakkoupis and Thomas Sauerwald. 2012. Rumor spreading and vertex expansion. InProceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, Yuval Rabani (Ed.). SIAM, 1623–1641. doi:10.1137/1.9781611973099. 129

    work page doi:10.1137/1.9781611973099 2012

  18. [18]

    George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. 2014. Randomized rumor spreading in dynamic graphs. InInternational Colloquium on Automata, Languages, and Programming. Springer, 495–507

    2014

  19. [19]

    George Giakkoupis and Philipp Woelfel. 2011. On the Randomness Requirements of Rumor Spreading. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, Dana Randall (Ed.). SIAM, 449–461. doi:10.1137/1.9781611973082.36

    work page doi:10.1137/1.9781611973082.36 2011

  20. [20]

    Robert Gmyr and Gopal Pandurangan. 2018. Time-Message Trade-Offs in Distributed Algorithms. In32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 32–1

    2018

  21. [21]

    Bernhard Haeupler. 2013. Simple, fast and deterministic gossip and rumor spreading. InProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. 705–716

    2013

  22. [22]

    Bernhard Haeupler. 2015. Simple, fast and deterministic gossip and rumor spreading.Journal of the ACM (JACM)62, 6 (2015), 1–18

    2015

  23. [23]

    Bernhard Haeupler and David Wajc. 2016. A Faster Distributed Radio Broadcast Primitive: Extended Abstract. InProceedings of the 2016 ACM Symposium on Principles of Distributed Computing(Chicago, Illinois, USA)(PODC ’16). Association for Computing Machinery, New York, NY, USA, 361–370. doi:10.1145/2933057.2933121

    work page doi:10.1145/2933057.2933121 2016

  24. [24]

    Hossein Jowhari, Mert Saglam, and Gábor Tardos. 2011. Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, Maurizio Lenzerini and Thomas Schwentick (Eds.). ACM, 49–58. doi:10.1145/19892...

    work page doi:10.1145/1989284.1989289 2011

  25. [25]

    Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking. 2000. Randomized rumor spreading. InProceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 565–574. Manuscript submitted to ACM 28 Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan

    2000

  26. [26]

    Miller, Richard Peng, and Shen Chen Xu

    Gary L. Miller, Richard Peng, and Shen Chen Xu. 2013. Parallel Graph Decompositions Using Random Shifts. InProceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures(Montréal, Québec, Canada)(SPAA ’13). Association for Computing Machinery, New York, NY, USA, 196–203. doi:10.1145/2486159.2486180

    work page doi:10.1145/2486159.2486180 2013

  27. [27]

    2017.Probability and computing: randomization and probabilistic techniques in algorithms and data analysis

    Michael Mitzenmacher and Eli Upfal. 2017.Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press

    2017

  28. [28]

    Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2018. Fast distributed algorithms for connectivity and MST in large graphs.ACM Transactions on Parallel Computing (TOPC)5, 1 (2018), 1–22

    2018

  29. [29]

    David Peleg and Vitaly Rubinovich. 2000. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction.SIAM J. Comput.30, 5 (2000), 1427–1442

    2000

  30. [30]

    Boris Pittel. 1987. On spreading a rumor.SIAM J. Appl. Math.47, 1 (1987), 213–223

    1987

  31. [31]

    Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2012. Distributed Verification and Hardness of Distributed Approximation.SIAM J. Comput.41, 5 (2012), 1235–1265. Manuscript submitted to ACM

    2012