Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

A New Perspective on Randomized Gossip Algorithms

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 the 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 gos- sip 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.

up
0 users have voted:

Paper Details

Authors:
Nicolas Loizou, Peter Richtarik
Submitted On:
5 December 2016 - 8:10am
Short Link:
Type:
Poster
Event:
Presenter's Name:
Nicolas Loizou
Paper Code:
1457
Document Year:
2016
Cite

Document Files

PosterGlobalSip.pdf

(121 downloads)

Subscribe

[1] Nicolas Loizou, Peter Richtarik , "A New Perspective on Randomized Gossip Algorithms", IEEE SigPort, 2016. [Online]. Available: http://sigport.org/1344. Accessed: Jul. 27, 2017.
@article{1344-16,
url = {http://sigport.org/1344},
author = {Nicolas Loizou; Peter Richtarik },
publisher = {IEEE SigPort},
title = {A New Perspective on Randomized Gossip Algorithms},
year = {2016} }
TY - EJOUR
T1 - A New Perspective on Randomized Gossip Algorithms
AU - Nicolas Loizou; Peter Richtarik
PY - 2016
PB - IEEE SigPort
UR - http://sigport.org/1344
ER -
Nicolas Loizou, Peter Richtarik . (2016). A New Perspective on Randomized Gossip Algorithms. IEEE SigPort. http://sigport.org/1344
Nicolas Loizou, Peter Richtarik , 2016. A New Perspective on Randomized Gossip Algorithms. Available at: http://sigport.org/1344.
Nicolas Loizou, Peter Richtarik . (2016). "A New Perspective on Randomized Gossip Algorithms." Web.
1. Nicolas Loizou, Peter Richtarik . A New Perspective on Randomized Gossip Algorithms [Internet]. IEEE SigPort; 2016. Available from : http://sigport.org/1344