Title :
On the convergence time of distributed quantized averaging algorithms
Author :
Zhu, Minghui ; Martínez, Sonia
Author_Institution :
Dept. of Mech. & Aerosp. Eng., Univ. of California, La Jolla, CA, USA
Abstract :
We come up with novel quantized averaging algorithms on synchronous and asynchronous communication networks with fixed, switching and random topologies. The implementation of these algorithms is subject to the realistic constraint that the communication rate, the memory capacities of agents and the computation precision are finite. The focus of this paper is on the study of the convergence time of the proposed quantized averaging algorithms. By appealing to random walks on graphs, we derive polynomial bounds on the expected convergence time of all the algorithms presented.
Keywords :
computational complexity; convergence; distributed algorithms; network theory (graphs); telecommunication network topology; telecommunication switching; asynchronous communication network switching; convergence time; distributed quantized averaging algorithm; graph theory; polynomial bound; random topology; synchronous communication network; Asynchronous communication; Channel capacity; Communication channels; Communication networks; Communication switching; Convergence; Load management; Network topology; Polynomials; Quantization;
Conference_Titel :
Decision and Control, 2008. CDC 2008. 47th IEEE Conference on
Conference_Location :
Cancun
Print_ISBN :
978-1-4244-3123-6
Electronic_ISBN :
0191-2216
DOI :
10.1109/CDC.2008.4738749