Abstract

In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of O(nmD log n) for the expected convergence time to consensus, where n, m and D, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of log n for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs.

Original languageEnglish (US)
Article number7117385
Pages (from-to)443-455
Number of pages13
JournalIEEE Transactions on Automatic Control
Volume61
Issue number2
DOIs
StatePublished - Feb 2016

Fingerprint

Markov processes
Time varying networks
Harmonic functions

Keywords

  • Convergence time
  • Markov chains
  • quantized consensus
  • random walk
  • spectral representation
  • time varying networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

Convergence Time for Unbiased Quantized Consensus over Static and Dynamic Networks. / Etesami, Seyed Rasoul; Basar, M Tamer.

In: IEEE Transactions on Automatic Control, Vol. 61, No. 2, 7117385, 02.2016, p. 443-455.

Research output: Contribution to journalArticle

@article{e76664f9b2834dbe883c09a25b7b669a,
title = "Convergence Time for Unbiased Quantized Consensus over Static and Dynamic Networks",
abstract = "In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of O(nmD log n) for the expected convergence time to consensus, where n, m and D, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of log n for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs.",
keywords = "Convergence time, Markov chains, quantized consensus, random walk, spectral representation, time varying networks",
author = "Etesami, {Seyed Rasoul} and Basar, {M Tamer}",
year = "2016",
month = "2",
doi = "10.1109/TAC.2015.2440568",
language = "English (US)",
volume = "61",
pages = "443--455",
journal = "IEEE Transactions on Automatic Control",
issn = "0018-9286",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - Convergence Time for Unbiased Quantized Consensus over Static and Dynamic Networks

AU - Etesami, Seyed Rasoul

AU - Basar, M Tamer

PY - 2016/2

Y1 - 2016/2

N2 - In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of O(nmD log n) for the expected convergence time to consensus, where n, m and D, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of log n for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs.

AB - In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of O(nmD log n) for the expected convergence time to consensus, where n, m and D, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of log n for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs.

KW - Convergence time

KW - Markov chains

KW - quantized consensus

KW - random walk

KW - spectral representation

KW - time varying networks

UR - http://www.scopus.com/inward/record.url?scp=84961999208&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961999208&partnerID=8YFLogxK

U2 - 10.1109/TAC.2015.2440568

DO - 10.1109/TAC.2015.2440568

M3 - Article

AN - SCOPUS:84961999208

VL - 61

SP - 443

EP - 455

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

SN - 0018-9286

IS - 2

M1 - 7117385

ER -