Acceleration of Gossip Algorithms through the Euler-Poisson-Darboux Equation

Raphaël Berthier, Mufan Li

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.