Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders

Abstract

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 $\hat{I}˜(\log n)$ rounds, we prove that our $k$-PUSH&PULL variant completes in $\hat{I}˜({\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 $\ddot{I}•>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 }_{\ddot{I}}•n\cdot {\log }_{k}n)$ rounds in these expanders, with high probability. We complement this with a simple lower bound of $\hat{I}\text{c◯}({\log }_{\ddot{I}}•n+{\log }_{k}n)$ rounds.

To appear at DISC 2025