Journal
AUTOMATICA
Volume 50, Issue 2, Pages 635-640Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.automatica.2013.11.034
Keywords
Consensus; Distributed computation; Algebraic graph theory; Graph eigenvalues; Distance-regular graphs
Funding
- Interuniversity Attraction Poles Programme
- Belgian State, Science Policy Office
- Concerted Research Action (ARC) of the French Community of Belgium
Ask authors/readers for more resources
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 9, 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. (C) 2013 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available