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 -