Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]–[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.


Published in:
Proceedings ISIT'10
Presented at:
IEEE International Symposium on Information Theory, Austin, Texas, USA, June 13-18, 2010
Year:
2010
Publisher:
IEEE
Keywords:
Laboratories:




 Record created 2010-05-10, last modified 2018-03-18

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)