Broadcast Gossip Algorithms for Consensus

Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibl...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2009-07, Vol.57 (7), p.2748-2761
Main Authors: Aysal, T.C., Yildiz, M.E., Sarwate, A.D., Scaglione, A.
Format: Article
Language:English
Subjects:
Ad hoc networks
Algorithms
Applied sciences
Balancing
Broadcasting
Computation
Computer networks
Convergence
Convergence of numerical methods
Costs
Detection, estimation, filtering, equalization, prediction
distributed average consensus
Distributed computing
Error analysis
Exact sciences and technology
gossip algorithms
Information, signal and communications theory
Mean square error methods
Miscellaneous
Networks
Peer to peer computing
sensor networks
Signal and communications theory
Signal processing
Signal, noise
Studies
Telecommunications and information theory
Velocity measurement
Wireless communication
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithm converges almost surely to a consensus. We prove that the random consensus value is, in expectation, the average of initial node measurements and that it can be made arbitrarily close to this value in mean squared error sense, under a balanced connectivity model and by trading off convergence speed with accuracy of the computation. We provide theoretical and numerical results on the mean square error performance, on the convergence rate and study the effect of the ldquomixing parameterrdquo on the convergence rate of the broadcast gossip algorithm. The results indicate that the mean squared error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithm to achieve a given distance to consensus through theoretical and numerical results.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2009.2016247