On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations

Mario Coutino; Elvin Isufi; Takanori Maehara; Geert Leus

doi:10.1109/ACSSC.2018.8645186

On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations

Mario Coutino, Elvin Isufi, Takanori Maehara, Geert Leus

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

4 Citations (Scopus)

20 Downloads (Pure)

Abstract

In this work, we explore the limits of finite-time distributed consensus through the intersection of graph filters and matrix function theory. We focus on algorithms capable to compute the consensus exactly through filtering operations over a graph, and that have been proven to converge in finite time. In this context, we show that there exists an algebraic algorithm that can minimize the minimum polynomial of a matrix whose support is known. Different from previous works, we leverage the structure of matrices that share the same support and are diagonalizable by the eigenbasis of the graph shift operator to prove a theoretical result with respect to the minimum number of diffusion steps required to reach consensus. We show that the previously known bound on the number of consensus iterations can be further reduced in accordance to the algebraic properties of the matrix representation of the network. Finally, insights with respect to the relation between the graph topology and the algebraic properties of such matrices are provided in order to encourage further discussion on the role of eigenvalues and eigenvectors in the network topology.

Original language	English
Title of host publication	2018 52nd Asilomar Conference on Signals, Systems, and Computers
Editors	Michael B. Matthews
Place of Publication	Piscataway, NJ, USA
Publisher	IEEE
Pages	993-997
Number of pages	5
ISBN (Electronic)	978-1-5386-9218-9
ISBN (Print)	978-1-5386-9219-6
DOIs	https://doi.org/10.1109/ACSSC.2018.8645186
Publication status	Published - 2019
Event	52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 - Pacific Grove, United States Duration: 28 Oct 2018 → 31 Oct 2018

Conference

Conference	52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Country/Territory	United States
City	Pacific Grove
Period	28/10/18 → 31/10/18

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Consensus
distributed averaging
graph filters
signal processing over networks

Access to Document

10.1109/ACSSC.2018.8645186

On_The_Limits_of_Finite-Time_Distributed_Consensus_Through_Successive_Local_Linear_OperationsFinal published version, 156 KB

Cite this

@inproceedings{7e2b8cd25bc34c4486152c83437eb50c,

title = "On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations",

abstract = "In this work, we explore the limits of finite-time distributed consensus through the intersection of graph filters and matrix function theory. We focus on algorithms capable to compute the consensus exactly through filtering operations over a graph, and that have been proven to converge in finite time. In this context, we show that there exists an algebraic algorithm that can minimize the minimum polynomial of a matrix whose support is known. Different from previous works, we leverage the structure of matrices that share the same support and are diagonalizable by the eigenbasis of the graph shift operator to prove a theoretical result with respect to the minimum number of diffusion steps required to reach consensus. We show that the previously known bound on the number of consensus iterations can be further reduced in accordance to the algebraic properties of the matrix representation of the network. Finally, insights with respect to the relation between the graph topology and the algebraic properties of such matrices are provided in order to encourage further discussion on the role of eigenvalues and eigenvectors in the network topology.",

keywords = "Consensus, distributed averaging, graph filters, signal processing over networks",

author = "Mario Coutino and Elvin Isufi and Takanori Maehara and Geert Leus",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 ; Conference date: 28-10-2018 Through 31-10-2018",

year = "2019",

doi = "10.1109/ACSSC.2018.8645186",

language = "English",

isbn = "978-1-5386-9219-6 ",

pages = "993--997",

editor = "Matthews, {Michael B.}",

booktitle = "2018 52nd Asilomar Conference on Signals, Systems, and Computers",

publisher = "IEEE",

address = "United States",

}

Coutino, M, Isufi, E, Maehara, T & Leus, G 2019, On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations. in MB Matthews (ed.), 2018 52nd Asilomar Conference on Signals, Systems, and Computers., 8645186, IEEE, Piscataway, NJ, USA, pp. 993-997, 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018, Pacific Grove, United States, 28/10/18. https://doi.org/10.1109/ACSSC.2018.8645186

On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations. / Coutino, Mario; Isufi, Elvin; Maehara, Takanori et al.
2018 52nd Asilomar Conference on Signals, Systems, and Computers. ed. / Michael B. Matthews. Piscataway, NJ, USA: IEEE, 2019. p. 993-997 8645186.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations

AU - Coutino, Mario

AU - Isufi, Elvin

AU - Maehara, Takanori

AU - Leus, Geert

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2019

Y1 - 2019

N2 - In this work, we explore the limits of finite-time distributed consensus through the intersection of graph filters and matrix function theory. We focus on algorithms capable to compute the consensus exactly through filtering operations over a graph, and that have been proven to converge in finite time. In this context, we show that there exists an algebraic algorithm that can minimize the minimum polynomial of a matrix whose support is known. Different from previous works, we leverage the structure of matrices that share the same support and are diagonalizable by the eigenbasis of the graph shift operator to prove a theoretical result with respect to the minimum number of diffusion steps required to reach consensus. We show that the previously known bound on the number of consensus iterations can be further reduced in accordance to the algebraic properties of the matrix representation of the network. Finally, insights with respect to the relation between the graph topology and the algebraic properties of such matrices are provided in order to encourage further discussion on the role of eigenvalues and eigenvectors in the network topology.

AB - In this work, we explore the limits of finite-time distributed consensus through the intersection of graph filters and matrix function theory. We focus on algorithms capable to compute the consensus exactly through filtering operations over a graph, and that have been proven to converge in finite time. In this context, we show that there exists an algebraic algorithm that can minimize the minimum polynomial of a matrix whose support is known. Different from previous works, we leverage the structure of matrices that share the same support and are diagonalizable by the eigenbasis of the graph shift operator to prove a theoretical result with respect to the minimum number of diffusion steps required to reach consensus. We show that the previously known bound on the number of consensus iterations can be further reduced in accordance to the algebraic properties of the matrix representation of the network. Finally, insights with respect to the relation between the graph topology and the algebraic properties of such matrices are provided in order to encourage further discussion on the role of eigenvalues and eigenvectors in the network topology.

KW - Consensus

KW - distributed averaging

KW - graph filters

KW - signal processing over networks

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

U2 - 10.1109/ACSSC.2018.8645186

DO - 10.1109/ACSSC.2018.8645186

M3 - Conference contribution

AN - SCOPUS:85062991075

SN - 978-1-5386-9219-6

SP - 993

EP - 997

BT - 2018 52nd Asilomar Conference on Signals, Systems, and Computers

A2 - Matthews, Michael B.

PB - IEEE

CY - Piscataway, NJ, USA

T2 - 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018

Y2 - 28 October 2018 through 31 October 2018

ER -

On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this