Linear time average consensus on fixed graphs

Alex Olshevsky

doi:10.1016/j.ifacol.2015.10.313

Linear time average consensus on fixed graphs

Alex Olshevsky

Research output: Contribution to journal › Conference article › peer-review

Abstract

We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes n. More precisely we provide a protocol which results in each node having a value within an e of the initial average after O (Equation presented) iterations. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound U on the total number of nodes which is correct within a. constant multiplicative factor.

Original language	English (US)
Pages (from-to)	94-99
Number of pages	6
Journal	IFAC-PapersOnLine
Volume	48
Issue number	22
DOIs	https://doi.org/10.1016/j.ifacol.2015.10.313
State	Published - Oct 1 2015

Keywords

Consensus and gossip algorithms
Cooperative control
Distributed algorithms
Markov chains
Multi-agent systems

ASJC Scopus subject areas

Control and Systems Engineering

Online availability

10.1016/j.ifacol.2015.10.313

Library availability

Discover UIUC Full Text

Cite this

@article{da01c0215507422ebb874e1940f6d926,

title = "Linear time average consensus on fixed graphs",

abstract = "We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes n. More precisely we provide a protocol which results in each node having a value within an e of the initial average after O (Equation presented) iterations. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound U on the total number of nodes which is correct within a. constant multiplicative factor.",

keywords = "Consensus and gossip algorithms, Cooperative control, Distributed algorithms, Markov chains, Multi-agent systems",

author = "Alex Olshevsky",

note = "Publisher Copyright: {\textcopyright} 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved. Copyright: Copyright 2016 Elsevier B.V., All rights reserved.",

year = "2015",

month = oct,

day = "1",

doi = "10.1016/j.ifacol.2015.10.313",

language = "English (US)",

volume = "48",

pages = "94--99",

journal = "IFAC-PapersOnLine",

issn = "2405-8963",

publisher = "IFAC Secretariat",

number = "22",

}

TY - JOUR

T1 - Linear time average consensus on fixed graphs

AU - Olshevsky, Alex

PY - 2015/10/1

Y1 - 2015/10/1

N2 - We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes n. More precisely we provide a protocol which results in each node having a value within an e of the initial average after O (Equation presented) iterations. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound U on the total number of nodes which is correct within a. constant multiplicative factor.

AB - We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes n. More precisely we provide a protocol which results in each node having a value within an e of the initial average after O (Equation presented) iterations. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound U on the total number of nodes which is correct within a. constant multiplicative factor.

KW - Consensus and gossip algorithms

KW - Cooperative control

KW - Distributed algorithms

KW - Markov chains

KW - Multi-agent systems

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

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

U2 - 10.1016/j.ifacol.2015.10.313

DO - 10.1016/j.ifacol.2015.10.313

M3 - Conference article

SN - 2405-8963

VL - 48

SP - 94

EP - 99

JO - IFAC-PapersOnLine

JF - IFAC-PapersOnLine

IS - 22

ER -

Linear time average consensus on fixed graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

5th IFAC Workshop on Distributed Estimation and Control in Networked Systems NecSys 2015: Philadelphia, 10-11 September 2015

Cite this