Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

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

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.

Keywords: Distributed Signal Processing ; Gossip Algorithms ; Consensus ; NCCR-MICS ; NCCR-MICS/ESDM

Reference

• EPFL-CONF-148711

Record created on 2010-05-10, modified on 2017-05-12