标题： 面向小集扩张图的常数时间多调用谣言传播 显示英文标题

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

摘要： 我们研究了经典PUSH&PULL谣言传播过程的一个多调用变体，其中节点在PUSH和PULL操作期间可以联系$k$个邻居，而不是仅一个。 我们证明，通过增加节点之间的通信量，可以使谣言传播更快。 作为一个激励性例子，考虑一个包含$n$个节点的完全图上的过程：虽然标准的PUSH&PULL协议需要$\Theta(\log n)$轮，但我们证明我们的$k$-PUSH&PULL变体以高概率在$\Theta(\log_{k} n)$轮内完成。 我们以一种与扩展敏感的方式推广这一结果，正如对经典PUSH&PULL协议的不同扩展概念（例如，导通性和顶点扩展）所做的那样。 我们考虑小集顶点扩展器，即每个足够小的节点子集都有一个大的邻域的图，确保强大的局部连通性。 特别是，当扩展参数满足$\phi > 1$时，这些图的直径为$o(\log n)$，与其他标准的扩展概念相反。 由于图的直径是谣言传播所需轮数的下限，这使得小集扩展器特别适合快速信息传播。 我们证明，在这些扩展器中，$k$-PUSH&PULL以高概率需要$O(\log_{\phi} n \cdot \log_{k} n)$轮。 我们通过一个简单的下界$\Omega(\log_{\phi} n+ \log_{k} n)$轮来补充这一点。 显示英文摘要

摘要： 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 $\Theta(\log n)$ rounds, we prove that our $k$-PUSH&PULL variant completes in $\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 $\phi > 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_{\phi} n \cdot \log_{k} n)$ rounds in these expanders, with high probability. We complement this with a simple lower bound of $\Omega(\log_{\phi} n+ \log_{k} n)$ rounds.