Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Reducing Communication Overhead for Average Consensus

Abstract : Average consensus is an iterative protocol where nodes in a network, each having an initial scalar value called estimate, perform a distributed algorithm to calculate the average of all estimates presented in the network by using only local communication. With every iteration, nodes receive the estimates from their neighbors, and they update their own estimate by the weighted average of the received ones. While the average consensus protocol converges asymptotically to consensus, implementing a termination algorithm is challenging when nodes are not aware of some global information (e.g. the diameter of the network or the number of nodes presented). In this report, we are interested in decreasing the rate of the messages sent in the network as the estimates are closer to consensus. We propose a totally distributed algorithm for average consensus where nodes send more messages when the nodes have large differences in their estimates, and reduce their rate of sending messages when the consensus is almost reached. The convergence of the system is guaranteed to be within a predefined margin from the true average and the communication overhead is largely reduced.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Mahmoud El Chamie Connect in order to contact the contributor
Submitted on : Wednesday, August 1, 2012 - 11:33:31 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:28 AM
Long-term archiving on: : Friday, November 2, 2012 - 2:30:37 AM


Files produced by the author(s)


  • HAL Id : hal-00720687, version 2



Mahmoud El Chamie, Giovanni Neglia, Konstantin Avrachenkov. Reducing Communication Overhead for Average Consensus. [Research Report] RR-8025, INRIA. 2012, pp.22. ⟨hal-00720687v2⟩



Record views


Files downloads