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

Raphaël Berthier, Mufan Bill Li

Abstract

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.

Introduction

In large-scale decentralized networks, such as sensor arrays or peer-to-peer systems, there is often no central node to perform global calculations. Instead, nodes use gossip algorithms, repeatedly exchanging and averaging values with their neighbors to converge on a global average.

However, "simple gossip" is notoriously slow on grid-like networks. It suffers from a "diffusivity problem," where information spreads like heat through a metal rod—quickly at first, but taking a very long time to reach distant parts of the system. While accelerated versions exist, they often rely on complex algebra. This paper provides a clear, physical model for why these accelerated methods work better by showing they follow the Euler–Poisson–Darboux (EPD) equation.

Methods: Scaling Limits

The authors employ a scaling limit approach, transforming discrete step-by-step updates into continuous Partial Differential Equations (PDEs) by imagining a massive network where both the number of iterations and nodes go to infinity.

  1. Simple Gossip to Heat Equation: The standard update rule (averaging with neighbors) is mathematically equivalent to the Heat Equation.
  2. Accelerated Gossip to EPD Equation: The "Jacobi polynomial iteration," a second-order method using "memory" of previous states, scales to the EPD equation, a wave equation with a specific damping term.
  3. Rigorous Proofs: Using Fourier analysis and the Mehler–Heine asymptotic properties of Jacobi polynomials, the authors rigorously prove these convergence limits on regular lattices ($\mathbb{Z}^d$).

Key Insights and Results

The "Ideal" Gossip Shape

The fundamental solution to the EPD equation is a uniform density over an expanding ellipsoid. This is the "holy grail" of gossip: information spreads at a constant speed ($t$) rather than the square root of time ($\sqrt{t}$), and it distributes itself perfectly evenly within that expanding boundary. Accelerated gossip works by giving "inertia" to the information, pushing it outward aggressively while the damping term prevents infinite oscillation.

Visual Validation

Simulations on line graphs ($\mathbb{Z}$) and lattices ($\mathbb{Z}^2$) validate the theory. As shown in the figures below, as the number of iterations $n$ increases, the discrete algorithm's behavior matches the continuous PDE solution with remarkable accuracy.

Comparison of discrete gossip algorithms (simple and accelerated) with their continuous PDE limits (Heat and EPD equations) on a line graph for increasing iterations $n$.

Performance Gains

  • Speedup: Accelerated gossip spreads information on a scale of $\|y\| \approx t$, whereas simple gossip only reaches $\|y\| \approx \sqrt{t}$.
  • Convergence Rates: For a $d$-dimensional lattice, the error for accelerated gossip decays at a rate of $1/n^d$, significantly faster than the $1/n^{d/2}$ rate of simple gossip.

Limitations and Future Work

While the results are promising, the rigorous proofs currently apply only to regular, translation-invariant lattices and assume synchronous communication. A major open question is whether these results hold for "messy" graphs, like random geometric graphs. The authors suspect the "homogenization" principle applies—meaning large-scale behavior should still resemble these PDEs—but the mathematical proof remains for future work.

Summary updated

Abstract

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.
BibTeX
@misc{berthier2022acceleration,
  author = {Raphaël Berthier and Mufan Bill Li},
  title = {{Acceleration of Gossip Algorithms through the Euler-Poisson-Darboux Equation}},
  year = {2022},
  eprint = {2202.10742},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.10742},
}
Figure