Gossip algorithms and their accelerated versions have been studied exclusively in discrete time on graphs. In this work, we take a different approach, and consider the scaling limit of gossip algorithms in both large graphs and large number of iterations. These limits lead to well-known partial differential equations (PDEs) with insightful properties. On lattices, we prove that the non-accelerated gossip algorithm of Boyd et al. [2006] converges to the heat equation, and the accelerated Jacobi polynomial iteration of Berthier et al. [2020] converges to the Euler-Poisson-Darboux (EPD) equation - a damped wave equation. Remarkably, with appropriate parameters, the fundamental solution of the EPD equation has the ideal gossip behaviour: a uniform density over an ellipsoid, whose radius increases at a rate proportional to t - the fastest possible rate for locally communicating gossip algorithms. This is in contrast with the heat equation where the density spreads on a typical scale of $\sqrt{t}$. Additionally, we provide simulations demonstrating that the gossip algorithms are accurately approximated by their limiting PDEs.

翻译：Gossip 算法及其加速版本在图表上的离散时间专门研究。 在这项工作中, 我们采取了不同的方法, 并考虑了大图表和大量迭代中八卦算法的缩放限制。 这些限制导致众所周知的局部差异方程式( PDEs ), 具有有洞察力的特性。 在 lattices 上, 我们证明 Boyd et al. [ 2006] 的非加速八卦算法及其加速版本与热方程相匹配, 以及 Berthier 等人( 20202020 ) 加速的 coupi 多元代谢变等式与 Euler- Poisson- Darbuux ( ELPD) 等式相交汇 — 一种倾斜波方程式。 在有适当参数的情况下, EPDD 等式的基本解决方案具有理想的八流行为: 一种统一的密度, 其半径与 t 的比例增长 — 当地传播八理算算算算法的最快速度率。 这与热方程式形成对照, 其密度在典型的 $\ qrt{ t} 。 此外, 我们提供了精确的模拟分析。