Graph diameter, eigenvalues, and minimum-time consensus

Julien M. Hendrickx, Raphaël M. Jungers, Alexander Olshevsky, Guillaume Vankeerberghen

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of achieving average consensus in the minimum number of linear iterations on a fixed, undirected graph. We are motivated by the task of deriving lower bounds for consensus protocols and by the so-called "definitive consensus conjecture", which states that for an undirected connected graph G with diameter D there exist D matrices whose nonzero-pattern complies with the edges in G and whose product equals the all-ones matrix. Our first result is a counterexample to the definitive consensus conjecture, which is the first improvement of the diameter lower bound for linear consensus protocols. We then provide some algebraic conditions under which this conjecture holds, which we use to establish that all distance-regular graphs satisfy the definitive consensus conjecture.

Original languageEnglish (US)
Pages (from-to)635-640
Number of pages6
JournalAutomatica
Volume50
Issue number2
DOIs
StatePublished - Feb 2014

Keywords

  • Algebraic graph theory
  • Consensus
  • Distance-regular graphs
  • Distributed computation
  • Graph eigenvalues

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Graph diameter, eigenvalues, and minimum-time consensus'. Together they form a unique fingerprint.

Cite this