A New Perspective on Randomized Gossip Algorithms

Nicolas Loizou, Peter Richtárik

Research output: Contribution to conferencePaperpeer-review

Abstract

In this short note we propose a new approach for the design and analysis of randomized gossip algorithms which can be used to solve the average consensus problem. We show how that Randomized Block Kaczmarz (RBK) method - a method for solving linear systems - works as gossip algorithm when applied to a special system encoding the underlying network. The famous pairwise gossip algorithm arises as a special case. Subsequently, we reveal a hidden duality of randomized gossip algorithms, with the dual iterative process maintaining a set of numbers attached to the edges as opposed to nodes of the network. We prove that RBK obtains a superlinear speedup in the size of the block, and demonstrate this effect through experiments.
Original languageEnglish
Publication statusPublished - 24 Apr 2017
Event2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Washington, United States
Duration: 7 Dec 20169 Dec 2016

Conference

Conference2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016
CountryUnited States
CityWashington
Period7/12/169/12/16

Keywords

  • cs.DC
  • cs.IT
  • math.IT
  • math.OC

Fingerprint Dive into the research topics of 'A New Perspective on Randomized Gossip Algorithms'. Together they form a unique fingerprint.

Cite this