2026-09-13T04:32:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24843 2026-09-05T18:58:59Z ddc:004 open_access

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders Cruciani, Emilio Forster, Sebastian de Vos, Tijn small set expansion vertex expansion rumor spreading multi-call rumor spreading push&pull protocol We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact 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 nodes: while the standard PUSH&PULL protocol takes Θ(log n) rounds, we prove that our k-PUSH&PULL variant completes in Θ(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, these graphs have a diameter of 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-PUSH&PULL takes O(log_{ϕ} n ⋅ log_{k} n) rounds in these expanders, with high probability. We complement this with a simple lower bound of Ω(log_{ϕ} n+ log_{k} n) rounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emilio Cruciani and Sebastian Forster and Tijn de Vos 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.26 urn:nbn:de:0030-drops-248434 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode