Skip to Main content Skip to Navigation
Reports

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
Complete list of metadata

https://hal.inria.fr/hal-00720687
Contributor : Mahmoud El Chamie <>
Submitted on : Wednesday, August 1, 2012 - 11:33:31 AM
Last modification on : Wednesday, October 14, 2020 - 3:57:38 AM
Long-term archiving on: : Friday, November 2, 2012 - 2:30:37 AM

File

RR-8025.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00720687, version 2

Collections

Citation

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

Share

Metrics

Record views

563

Files downloads

239