Convergence Time of Quantized Metropolis Consensus over Time-Varying Networks

Research output: Contribution to journalArticle

Abstract

We consider the quantized consensus problem on undirected time-varying connected graphs with n nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n 2 log 2 n) , where each node performs a constant number of updates per unit time.

Original languageEnglish (US)
Article number7428833
Pages (from-to)4048-4854
Number of pages807
JournalIEEE Transactions on Automatic Control
Volume61
Issue number12
DOIs
StatePublished - Dec 2016

Fingerprint

Time varying networks

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 of Quantized Metropolis Consensus over Time-Varying Networks. / Basar, M Tamer; Etesami, Seyed Rasoul; Olshevsky, Alex.

In: IEEE Transactions on Automatic Control, Vol. 61, No. 12, 7428833, 12.2016, p. 4048-4854.

Research output: Contribution to journalArticle

@article{9d551ef04eb849dab4c1a665e6e13032,
title = "Convergence Time of Quantized Metropolis Consensus over Time-Varying Networks",
abstract = "We consider the quantized consensus problem on undirected time-varying connected graphs with n nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n 2 log 2 n) , where each node performs a constant number of updates per unit time.",
keywords = "Convergence time, Markov chains, quantized consensus, random walk, spectral representation, time varying networks",
author = "Basar, {M Tamer} and Etesami, {Seyed Rasoul} and Alex Olshevsky",
year = "2016",
month = "12",
doi = "10.1109/TAC.2016.2539547",
language = "English (US)",
volume = "61",
pages = "4048--4854",
journal = "IEEE Transactions on Automatic Control",
issn = "0018-9286",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "12",

}

TY - JOUR

T1 - Convergence Time of Quantized Metropolis Consensus over Time-Varying Networks

AU - Basar, M Tamer

AU - Etesami, Seyed Rasoul

AU - Olshevsky, Alex

PY - 2016/12

Y1 - 2016/12

N2 - We consider the quantized consensus problem on undirected time-varying connected graphs with n nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n 2 log 2 n) , where each node performs a constant number of updates per unit time.

AB - We consider the quantized consensus problem on undirected time-varying connected graphs with n nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n 2 log 2 n) , where each node performs a constant number of updates per unit time.

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=85003881501&partnerID=8YFLogxK

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

U2 - 10.1109/TAC.2016.2539547

DO - 10.1109/TAC.2016.2539547

M3 - Article

AN - SCOPUS:85003881501

VL - 61

SP - 4048

EP - 4854

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

SN - 0018-9286

IS - 12

M1 - 7428833

ER -