Skip to Main content Skip to Navigation
Reports

Design and Analysis of Distributed Averaging with Quantized Communication

Abstract : Consider a network whose nodes have some initial values, and it is desired to design an algorithm that builds on neighbor to neighbor interactions with the ultimate goal of convergence to the average of all initial node values or to some value close to that average. Such an algorithm is called generically "distributed averaging," and our goal in this paper is to study the performance of a subclass of deterministic distributed averaging algorithms where the information exchange between neighboring nodes (agents) is subject to uniform quantization. With such quantization, convergence to the precise average cannot be achieved in general, but the convergence would be to some value close to it, called quantized consensus. Using Lyapunov stability analysis, we characterize the convergence properties of the resulting nonlinear quantized system. We show that in finite time and depending on initial conditions, the algorithm will either cause all agents to reach a quantized consensus where the consensus value is the largest quantized value not greater than the average of their initial values, or will lead all variables to cycle in a small neighborhood around the average. In the latter case, we identify tight bounds for the size of the neighborhood and we further show that the error can be made arbitrarily small by adjusting the algorithm's parameters in a distributed manner.
Document type :
Reports
Complete list of metadata

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-00960891
Contributor : Mahmoud El Chamie <>
Submitted on : Saturday, September 13, 2014 - 10:10:57 PM
Last modification on : Thursday, August 1, 2019 - 2:13:44 PM
Long-term archiving on: : Sunday, December 14, 2014 - 10:25:06 AM

Files

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

Identifiers

  • HAL Id : hal-00960891, version 2
  • ARXIV : 1403.4696

Collections

Citation

Mahmoud El Chamie, Ji Liu, Tamer Başar. Design and Analysis of Distributed Averaging with Quantized Communication. [Research Report] RR-8501, Inria. 2014, pp.33. ⟨hal-00960891v2⟩

Share

Metrics

Record views

207

Files downloads

658