A necessary and sufficient condition for consensus over random networks

Alireza Tahbaz-Salehi; Ali Jadbabaie

doi:10.1109/TAC.2008.917743

A necessary and sufficient condition for consensus over random networks

Alireza Tahbaz-Salehi^*, Ali Jadbabaie

^*Corresponding author for this work

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

325 Scopus citations

Abstract

We consider the consensus problem for stochastic discrete-time linear dynamical systems. The underlying graph of such systems at a given time instance is derived from a random graph process, independent of other time instances. For such a framework, we present a necessary and sufficient condition for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. This easily verifiable condition uses the spectrum of the average weight matrix. Finally, we investigate a special case for which the linear dynamical system converges to a fixed vector with probability 1.

Original language	English (US)
Pages (from-to)	791-795
Number of pages	5
Journal	IEEE Transactions on Automatic Control
Volume	53
Issue number	3
DOIs	https://doi.org/10.1109/TAC.2008.917743
State	Published - Apr 2008

Keywords

Consensus problem
Random graphs
Tail events
Weak ergodicity

ASJC Scopus subject areas

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/TAC.2008.917743

Fingerprint Dive into the research topics of 'A necessary and sufficient condition for consensus over random networks'. Together they form a unique fingerprint.

Cite this

@article{c4e2803093564adf88d2bd8426c78844,

title = "A necessary and sufficient condition for consensus over random networks",

abstract = "We consider the consensus problem for stochastic discrete-time linear dynamical systems. The underlying graph of such systems at a given time instance is derived from a random graph process, independent of other time instances. For such a framework, we present a necessary and sufficient condition for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. This easily verifiable condition uses the spectrum of the average weight matrix. Finally, we investigate a special case for which the linear dynamical system converges to a fixed vector with probability 1.",

keywords = "Consensus problem, Random graphs, Tail events, Weak ergodicity",

author = "Alireza Tahbaz-Salehi and Ali Jadbabaie",

year = "2008",

month = apr,

doi = "10.1109/TAC.2008.917743",

language = "English (US)",

volume = "53",

pages = "791--795",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

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

number = "3",

}

TY - JOUR

T1 - A necessary and sufficient condition for consensus over random networks

AU - Tahbaz-Salehi, Alireza

AU - Jadbabaie, Ali

PY - 2008/4

Y1 - 2008/4

N2 - We consider the consensus problem for stochastic discrete-time linear dynamical systems. The underlying graph of such systems at a given time instance is derived from a random graph process, independent of other time instances. For such a framework, we present a necessary and sufficient condition for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. This easily verifiable condition uses the spectrum of the average weight matrix. Finally, we investigate a special case for which the linear dynamical system converges to a fixed vector with probability 1.

AB - We consider the consensus problem for stochastic discrete-time linear dynamical systems. The underlying graph of such systems at a given time instance is derived from a random graph process, independent of other time instances. For such a framework, we present a necessary and sufficient condition for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. This easily verifiable condition uses the spectrum of the average weight matrix. Finally, we investigate a special case for which the linear dynamical system converges to a fixed vector with probability 1.

KW - Consensus problem

KW - Random graphs

KW - Tail events

KW - Weak ergodicity

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

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

U2 - 10.1109/TAC.2008.917743

DO - 10.1109/TAC.2008.917743

M3 - Article

AN - SCOPUS:42649100996

VL - 53

SP - 791

EP - 795

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

SN - 0018-9286

IS - 3

ER -