Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Acceleration of gossip algorithms through the Euler-Poisson-Darboux Equation
 
research article

Acceleration of gossip algorithms through the Euler-Poisson-Darboux Equation

Berthier, Raphael  
•
Li, Mufan (Bill)
November 26, 2022
Ima Journal Of Applied Mathematics

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 converges to the heat equation, and the accelerated Jacobi polynomial iteration of 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 root t. Additionally, we provide simulations demonstrating that the gossip algorithms are accurately approximated by their limiting PDEs.

  • Details
  • Metrics
Type
research article
DOI
10.1093/imamat/hxac029
Web of Science ID

WOS:000892389500001

Author(s)
Berthier, Raphael  
Li, Mufan (Bill)
Date Issued

2022-11-26

Publisher

OXFORD UNIV PRESS

Published in
Ima Journal Of Applied Mathematics
Subjects

Mathematics, Applied

•

Mathematics

•

gossip algorithms

•

euler-poisson-darboux equation

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MDS1  
Available on Infoscience
December 19, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/193323
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés