Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
Emilio Cruciani, Sebastian Forster, Tijn de Vos · 2025
Read Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders by Emilio Cruciani, Sebastian Forster, Tijn de Vos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18017.txt.
Introduction
Emilio Cruciani and co-authors study how gossip spreads faster when each node can call several neighbours per round, in a 2025 paper. In the classic push-pull process, informed nodes share a rumour and uninformed nodes ask for it, one contact at a time. Allowing many calls per round trades more chatter for speed.
On a fully connected network, the multi-call version finishes in far fewer rounds than the classic one. The team extends the result to well-connected sparse graphs where small sets of nodes reach many neighbours. There, total rounds depend on both the call count and the expansion strength. A lower bound sits close below the upper bound. The work maps the price of speed in added communication.
Catalog record
| CREATOR | Emilio Cruciani, Sebastian Forster, Tijn de Vos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-18017
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders Emilio Cruciani, Sebastian Forster, Tijn de Vos Abstract We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact k k of their neighbors instead of a single one during both PUSH and PULL operations. We show that rumor spreading can be made faster at the cost of an increased amount of communication between the nodes. As a motivating example, consider the process on a complete graph of n n nodes: while the standard PUSH&PULL protocol takes Θ ( log n ) \Theta(\log n) rounds, we prove that our k k - PUSH&PULL variant completes in Θ ( log k n ) \Theta(\log_{k}n) rounds, with high probability. We generalize this result in an expansion-sensitive way, as has been done for the classic PUSH&PULL protocol for different notions of expansion, e.g., conductance and vertex expansion. We consider small-set vertex expanders, graphs in which every sufficiently small subset of nodes has a large neighborhood, ensuring strong local connectivity. In particular, when the expansion parameter satisfies ϕ > 1 \phi>1 , these graphs have a diameter of o ( log n ) o(\log n) , as opposed to other standard notions of expansion. Since the graph’s diameter is a lower bound on the number of rounds required for rumor spreading, this makes small-set expanders particularly well-suited for fast information dissemination. We prove that k k - PUSH&PULL takes O ( log ϕ n ⋅ log k n ) O(\log_{\phi}n\cdot\log_{k}n) rounds in these expanders, with high probability. We complement this with a simple lower bound of Ω ( log ϕ n + log k n ) \Omega(\log_{\phi}n+\log_{k}n) rounds. Funding. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702) and is supported by the Austrian Science Fund (FWF): P 32863-N and P 36280-N. 1 Introduction Rumor spreading, which is loosely inspired by biological and social phenomena, is one of the most well-studied stochastic processes on graphs with a rich history in refined analyses [ 30 , 48 , 27 , 38 , 44 , 28 , 13 , 11 , 22 , 52 , 20 , 21 , 29 , 34 , 6 , 32 , 23 , 25 , 33 , 41 , 1 , 46 , 17 , 31 , 24 ] . In the classic random phone call model [ 19 ] , an arbitrary node of the graph initially knows a piece of information, the rumor, which spreads across the graph in synchronous rounds until eventually all nodes are informed. In each round, every node calls one of its neighbors uniformly at random: in the PUSH protocol each informed node informs the node it calls, in the PULL protocol each uninformed node is informed by the node it called, and in the PUSH&PULL protocol both of these information exchanges happen simultaneously. It is well known that PUSH , PULL , and PUSH&PULL on a complete graph with n nodes require \Theta(\log n) rounds to complete rumor spreading with high probability 1 1 1 We say that a statement holds with high probability (w.h.p. for short) if it holds with probability at least 1-n^{-c} , where c is a positive constant hidden in the asymptotic notation. [ 30 , 38 ] . Rumor spreading has been also extensively studied on expander graphs , with known tight bounds that relate the completion time of the process with different notions of expansion. In the following, we discuss only PUSH&PULL , due to strong lower bounds that exist for both PUSH and PULL in isolation [ 11 , 52 ] . In particular, the protocol with high probability requires \Theta(\varphi^{-1}\log n) rounds for graphs with conductance \varphi\in[0,1] [ 11 ] , and \Theta(\phi^{-1}\log n\log\Delta) rounds for graphs with maximum degree \Delta and vertex-expansion \phi\in[0,1] [ 34 , 32 ] . It is also known that PUSH&PULL requires \Omega(\sqrt{n}) rounds with high probability in graphs with constant edge-expansion [ 13 ] . The study of rumor spreading protocols on expanders, subsequently, has been used as a building block for designing distributed information dissemination algorithms [ 10 , 9 , 8 , 35 ] , some of which are based on expander decompositions [ 54 ] . Faster rumor spreading can be achieved on specific topologies or by modifying the process. On power-law degree distributed graphs, the process completes in O(\log\log n) rounds if the exponent of the power-law \beta is between 2 and 3 , while it needs \Omega(\log n) rounds if \beta is greater than 3 [ 29 ] . A variant of the process, where nodes can use direct addressing, i.e., are able to contact neighbors whose address was learned before, takes \Theta(\log\log n) rounds [ 36 , 6 ] . With the goal of making rumor spreading even faster, in this paper we study a multi-call variant of the classical protocol. We call this the k -PUSH&PULL protocol, where in each round every informed node samples k neighbors and sends the rumor to them, while every uninformed node samples k neighbors and requests the rumor from them. The sampling happens uniformly at random and with replacement in both PUSH and PULL operations. This process naturally interpolates between classical single-call rumor spreading and full broadcasting. It involves random selective communication, as in the former, while nodes simultaneously interact with multiple neighbors, as in the latter. This interpolation intuitively results in a trade-off between the amount of communication and the spreading time of the two processes. Classical rumor spreading requires minimal communication, while broadcasting is optimal in spreading time, matching the graph’s diameter in the worst case. Somewhat similar processes have been studied for the special case k=4 on random regular graphs [ 7 ] , with a randomized number of simultaneous calls on the complete graph [ 47 , 24 ] , and in the asynchronous setting considering multiple pulls on the complete graph [ 42 , 50 ] . For the related random-walk process, a multi-walk extension similar in spirit to our multi-call extension for rumor spreading has been studied by Alon et al. [ 2 ] . Apart from these works we are not aware of any paper studying the multi-call setting explicitly. While the analogy to a biological or social process might not be given anymore for the multi-call variant, we still believe that increasing the number of simultaneous calls is a quite natural generalization that captures a relevant aspect of information dissemination under bandwidth constraints. Furthermore, note that the classic “single-call” variant allows each node to receive multiple calls at the same time. 2 2 2 Restricted variants in which nodes receiving multiple calls can spread the rumor only to a single neighbor [ 17 ] cannot achieve performance guarantees comparable to the unrestricted variant in conductance expanders and vertex expanders [ 31 ] . Therefore, it seems natural to also allow nodes to initiate several calls at the same time. This leads to the central question of our work: Question: How much communication is required for sub-logarithmic