Acceleration of Gossip Algorithms through the Euler-Poisson-Darboux Equation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

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

Accélération des Algorithmes de Gossip par l'Equation d'Euler-Poisson-Darboux

Résumé

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.
Fichier principal
Vignette du fichier
epd.pdf (624.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03582008 , version 1 (21-02-2022)

Identifiants

  • HAL Id : hal-03582008 , version 1

Citer

Raphaël Berthier, Mufan Bill Li. Acceleration of Gossip Algorithms through the Euler-Poisson-Darboux Equation. 2022. ⟨hal-03582008⟩
43 Consultations
49 Téléchargements

Partager

Gmail Facebook X LinkedIn More