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

Conference paper (2019)

Authors

Mario Coutino RIKEN Center for Emergent Matter Science (CEMS), Signal Processing Systems - EEMCS
E. Isufi Signal Processing Systems - EEMCS ,
Takanori Maehara RIKEN Center for Emergent Matter Science (CEMS)
G.J.T. Leus Signal Processing Systems - EEMCS
Research Group
Signal Processing Systems (EEMCS) (TU Delft)
Copyright: © 2019 Mario Coutino, E. Isufi, Takanori Maehara, G.J.T. Leus
DOI: https://doi.org/10.1109/ACSSC.2018.8645186
Graph filters Consensus Distributed averaging Signal processing over networks
More Info
expand_more

Published Date

2019

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Microelectronics

Research Group

Signal Processing Systems

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.