Persistent graphs and consensus convergence

Guodong Shi; Karl Henrik Johansson

doi:10.1109/CDC.2012.6426728

Persistent graphs and consensus convergence

Guodong Shi^*, Karl Henrik Johansson

^*Corresponding author for this work

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

8 Citations (Scopus)

Abstract

This paper investigates the role persistent arcs play for averaging algorithms to reach a global consensus under discrete-time or continuous-time dynamics. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function. An arc is said to be persistent if its weight function has infinite ℒ₁ or ℓ₁ norm for continuous-time or discrete-time models, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or ε-agreement are established, by which we prove that the persistent graph fully determines the convergence to a consensus. It is also shown how the convergence rates explicitly depend on the diameter of the persistent graph.

Original language	English
Article number	6426728
Pages (from-to)	2046-2051
Number of pages	6
Journal	Proceedings of the IEEE Conference on Decision and Control
DOIs	https://doi.org/10.1109/CDC.2012.6426728
Publication status	Published - 2012
Externally published	Yes
Event	51st IEEE Conference on Decision and Control, CDC 2012 - Maui, HI, United States Duration: 10 Dec 2012 → 13 Dec 2012

Access to Document

10.1109/CDC.2012.6426728

Cite this

@article{7eaab9139e004224bc08d2608cbb2d0a,

title = "Persistent graphs and consensus convergence",

abstract = "This paper investigates the role persistent arcs play for averaging algorithms to reach a global consensus under discrete-time or continuous-time dynamics. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function. An arc is said to be persistent if its weight function has infinite ℒ1 or ℓ1 norm for continuous-time or discrete-time models, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or ε-agreement are established, by which we prove that the persistent graph fully determines the convergence to a consensus. It is also shown how the convergence rates explicitly depend on the diameter of the persistent graph.",

keywords = "Averaging Algorithms, Consensus, Persistent Graphs",

author = "Guodong Shi and Johansson, {Karl Henrik}",

year = "2012",

doi = "10.1109/CDC.2012.6426728",

language = "English",

pages = "2046--2051",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0743-1546",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "51st IEEE Conference on Decision and Control, CDC 2012 ; Conference date: 10-12-2012 Through 13-12-2012",

}

TY - JOUR

T1 - Persistent graphs and consensus convergence

AU - Shi, Guodong

AU - Johansson, Karl Henrik

PY - 2012

Y1 - 2012

N2 - This paper investigates the role persistent arcs play for averaging algorithms to reach a global consensus under discrete-time or continuous-time dynamics. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function. An arc is said to be persistent if its weight function has infinite ℒ1 or ℓ1 norm for continuous-time or discrete-time models, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or ε-agreement are established, by which we prove that the persistent graph fully determines the convergence to a consensus. It is also shown how the convergence rates explicitly depend on the diameter of the persistent graph.

AB - This paper investigates the role persistent arcs play for averaging algorithms to reach a global consensus under discrete-time or continuous-time dynamics. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function. An arc is said to be persistent if its weight function has infinite ℒ1 or ℓ1 norm for continuous-time or discrete-time models, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or ε-agreement are established, by which we prove that the persistent graph fully determines the convergence to a consensus. It is also shown how the convergence rates explicitly depend on the diameter of the persistent graph.

KW - Averaging Algorithms

KW - Consensus

KW - Persistent Graphs

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

U2 - 10.1109/CDC.2012.6426728

DO - 10.1109/CDC.2012.6426728

M3 - Conference article

AN - SCOPUS:84874267009

SN - 0743-1546

SP - 2046

EP - 2051

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

M1 - 6426728

T2 - 51st IEEE Conference on Decision and Control, CDC 2012

Y2 - 10 December 2012 through 13 December 2012

ER -

Persistent graphs and consensus convergence

Abstract

Access to Document

Other files and links

Fingerprint

Cite this