Broadcast gossip algorithms

Tuncer C. Aysal, Mehmet E. Yildiz, Anna Scaglione

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations


Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and for computing in an arbitrarily connected network of nodes. Specifically, we propose 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 algorithms almost surely converge to a consensus. In addition, the random consensus value is, in expectation, equal to the desired value, i.e., the average of initial node measurements. However, the broadcast gossip algorithms do not converge to the initial average in absolute sense because of the fact that the sum is not preserved at every iteration. We provide theoretical results on the mean square error performance of the broadcast gossip algorithms. The results indicate that the mean square error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithms required to achieve a given distance to consensus through numerical simulations.

Original languageEnglish (US)
Title of host publication2008 IEEE Information Theory Workshop, ITW
Number of pages5
StatePublished - Sep 22 2008
Externally publishedYes
Event2008 IEEE Information Theory Workshop, ITW - Porto, Portugal
Duration: May 5 2008May 9 2008

Publication series

Name2008 IEEE Information Theory Workshop, ITW


Other2008 IEEE Information Theory Workshop, ITW


  • Broadcasting
  • Distributed average consensus
  • Gossip algorithms
  • Sensor networks

ASJC Scopus subject areas

  • Information Systems
  • Electrical and Electronic Engineering


Dive into the research topics of 'Broadcast gossip algorithms'. Together they form a unique fingerprint.

Cite this