TY - JOUR

T1 - Graph diameter, eigenvalues, and minimum-time consensus

AU - Hendrickx, Julien M.

AU - Jungers, Raphaël M.

AU - Olshevsky, Alexander

AU - Vankeerberghen, Guillaume

N1 - Funding Information:
The authors would like to thank P. Van Dooren for the enlightening discussions they had with him. This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office , and the Concerted Research Action (ARC) of the French Community of Belgium . This work has benefited from many discussions within the FP7 NoE HYCON2. The scientific responsibility rests with its authors. R.M.J. is a F.R.S.-FNRS Research Associate, G.V. is a F.R.I.A. Fellow.

PY - 2014/2

Y1 - 2014/2

N2 - 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.

AB - 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.

KW - Algebraic graph theory

KW - Consensus

KW - Distance-regular graphs

KW - Distributed computation

KW - Graph eigenvalues

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

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

U2 - 10.1016/j.automatica.2013.11.034

DO - 10.1016/j.automatica.2013.11.034

M3 - Article

AN - SCOPUS:84893875458

SN - 0005-1098

VL - 50

SP - 635

EP - 640

JO - Automatica

JF - Automatica

IS - 2

ER -