On the asymptotic scalability of the consensus algorithm

Mehmet E. Yildiz, Anna Scaglione

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

2 Scopus citations


Average consensus algorithms are gossiping protocols for averaging original measurements taken at different sensors. Without any communication rate restrictions, the algorithms ideally allow every node state to converge to the initial average after some iterations. Noting that brute force quantization is highly suboptimal given the rich temporal and spatial correlation of the messages exchanged, in our previous work we proposed two source coding methods, predictive coding and Wyner-Ziv coding which achieve convergence with vanishing quantization rates in the case of block coding. Both methods ideally require complete information about the network parameters and topology as well as processing and storage of the past state values. The knowledge of the network parameters is not a practical requirement, especially considering that one is implementing average consensus algorithms that are decentralized. In this study we show that as the node density increases or in homogeneously distributed networks, the encoder and decoder parameters become independent on the network size and specific location. We also lower bound the error performance of the predictive coding scheme in terms of eigen-values of the connectivity and initial state covariance matrices. We show the relation between MSE behavior of the algorithm and network connectivity, as well as quantization rate.

Original languageEnglish (US)
Title of host publication2007 IEEE/SP 14th Workshop on Statistical Signal Processing, SSP 2007, Proceedings
Number of pages5
StatePublished - Dec 1 2007
Externally publishedYes
Event2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007 - Madison, WI, United States
Duration: Aug 26 2007Aug 29 2007

Publication series

NameIEEE Workshop on Statistical Signal Processing Proceedings


Other2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007
Country/TerritoryUnited States
CityMadison, WI


  • Communication systems
  • Distributed algorithms
  • Networks

ASJC Scopus subject areas

  • Signal Processing


Dive into the research topics of 'On the asymptotic scalability of the consensus algorithm'. Together they form a unique fingerprint.

Cite this