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 volumeConference contributionScientificpeer-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 languageEnglish
Title of host publication2018 52nd Asilomar Conference on Signals, Systems, and Computers
EditorsMichael B. Matthews
Place of PublicationPiscataway, NJ, USA
PublisherIEEE
Pages993-997
Number of pages5
ISBN (Electronic)978-1-5386-9218-9
ISBN (Print)978-1-5386-9219-6
DOIs
Publication statusPublished - 2019
Event52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 - Pacific Grove, United States
Duration: 28 Oct 201831 Oct 2018

Conference

Conference52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Country/TerritoryUnited States
CityPacific Grove
Period28/10/1831/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

Fingerprint

Dive into the research topics of 'On the Limits of Finite-Time Distributed Consensus Through Successive Local Linear Operations'. Together they form a unique fingerprint.

Cite this