A Caltech Library Service

On quantized consensus by means of gossip algorithm - Part II: Convergence time

Lavaei, Javad and Murray, Richard M. (2009) On quantized consensus by means of gossip algorithm - Part II: Convergence time. In: American Control Conference 2009 , Jun. 10-12, 2009, St. Louis, MO.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper deals with the distributed averaging problem over a connected network of agents, subject to a quantization constraint. It is assumed that at each time update, only a pair of agents can update their own numbers in terms of the quantized data being exchanged. The agents are also required to communicate with one another in a stochastic fashion. In the first part of the paper, it was shown that the quantized consensus is reached by means of a stochastic gossip algorithm proposed in a recent paper, for any arbitrary quantization. The current part of the paper considers the expected value of the time at which the quantized consensus is reached. This quantity (corresponding to the worst case) is lower and upper bounded in terms of the topology of the graph, for uniform quantization. In particular, it is shown that the upper bound is related to the principal minors of the weighted Laplacian matrix. A convex optimization is also proposed to determine the set of probabilities (used to pick a pair of agents) which leads to the fast convergence of the gossip algorithm.

Item Type:Conference or Workshop Item (Paper)
Related URLs:
Murray, Richard M. 0000-0002-5785-7481
Additional Information:© 2009 AACC.
Record Number:CaltechAUTHORS:20100507-091712132
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18178
Deposited By: Tony Diaz
Deposited On:10 May 2010 02:21
Last Modified:18 Mar 2015 23:02

Repository Staff Only: item control page