Randomized gossip algorithms for solving Laplacian systems

Anastasios Zouzias, Nikolaos M. Freris

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of solving a Laplacian system of equations Lx = b in a distributed fashion, where L is the Laplacian of the communication graph. Solving Laplacian systems arises in a number of applications including consensus, distributed control, clock synchronization, localization and calculating effective resistances, to name a few. We leverage our analysis on a randomized variant of Kaczmarz's algorithm to propose a distributed asynchronous gossip algorithm with expected exponential convergence. We quantify the convergence rate depending solely on properties of the network topology, and further propose an accelerated version that scales favorably for larger networks. Our approach naturally extends to least-squares estimation of general linear systems where each row/column is assigned to nodes of a given network. Last but not least, we show that average consensus is a special case in our framework.

Original languageEnglish (US)
Title of host publication2015 European Control Conference, ECC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9783952426937
StatePublished - Nov 16 2015
EventEuropean Control Conference, ECC 2015 - Linz, Austria
Duration: Jul 15 2015Jul 17 2015

Publication series

Name2015 European Control Conference, ECC 2015


OtherEuropean Control Conference, ECC 2015


  • Clock synchronization
  • Consensus
  • Cyberphysical systems
  • Distributed algorithms
  • Gossip algorithms
  • Laplacian systems
  • Randomized algorithms

ASJC Scopus subject areas

  • Control and Systems Engineering


Dive into the research topics of 'Randomized gossip algorithms for solving Laplacian systems'. Together they form a unique fingerprint.

Cite this