Diameter, Optimal Consensus, and Graph Eigenvalues

Julien M. Hendrickx, Raphaël M. Jungers, Alexander Olshevsky, Guillaume VankeerberghenarXiv 2012 · OpenReview

TL;DR

This paper challenges the long-held "definitive consensus conjecture," which proposed that average consensus could always be achieved in a number of linear iterations equal to a graph's diameter. The authors provide the first counterexample, demonstrating that some graphs require more steps. They then establish conditions under which the conjecture holds, proving it for all distance-regular graphs, and introduce the concept of a "consensus number" for graphs.

What Problem Does This Paper Address?

Distributed systems, from sensor networks to multi-agent robotics, often rely on "consensus algorithms" where individual agents (nodes) iteratively update their information based on their neighbors' states to reach a common agreement. A key goal is to achieve this agreement as quickly as possible, minimizing the number of communication rounds or "iterations." For a fixed network structure represented by an undirected graph, a natural question is: what is the minimum number of linear update steps required to guarantee average consensus for any initial state? The "definitive consensus conjecture" posited that this minimum number of steps is always equal to the graph's diameter (the longest shortest path between any two nodes). This paper investigates this conjecture, aiming to derive lower bounds on consensus protocols and to determine if the diameter is indeed the ultimate limit.

Methods

The authors approach this problem by framing it as a matrix problem. Each linear update step is represented by a matrix multiplication. Achieving average consensus after $D$ steps means finding $D$ matrices, $A^{(1)}, \dots, A^{(D)}$, that comply with the graph's structure (meaning non-zero entries only correspond to existing edges) and whose product $A^{(D)} \dots A^{(1)}$ results in a matrix where all entries are equal (specifically, $\frac{1}{N}\mathbf{1}\mathbf{1}^T$, where $N$ is the number of nodes and $\mathbf{1}$ is a vector of ones).

Their core contributions include:

  1. Counterexample Construction: They construct a specific graph (Gcx) with a diameter of 2 and demonstrate that no two matrices compliant with its structure can achieve average consensus. This directly refutes the definitive consensus conjecture.
  2. Algebraic Conditions for Consensus: They derive a set of algebraic conditions on a single matrix $M$ that, if met, guarantee the existence of $D$ compliant matrices for consensus. These conditions relate to the matrix's eigenvalues, minimal polynomial, and its ability to satisfy certain linear equations.
  3. Application to Distance-Regular Graphs: They show that distance-regular graphs (a class of highly symmetric graphs like cycles and complete graphs) satisfy these algebraic conditions, thus proving that the definitive consensus conjecture holds for this important family of graphs.
  4. Introduction of Consensus Number: They define the "consensus number" of a graph as the minimum number of steps required to achieve average consensus, which can be larger than the diameter.

Datasets

Not discussed in the paper. The paper focuses on theoretical graph properties and matrix algebra, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Diameter is Not Always the Limit: The most significant insight is that the diameter of a graph is not a strict lower bound for achieving average consensus using linear protocols. This overturns a long-standing conjecture and opens up new avenues for understanding consensus efficiency.
  • Symmetry Matters: The paper highlights that graphs with high symmetry, specifically distance-regular graphs, are more likely to satisfy the definitive consensus conjecture. This suggests a deep connection between graph structure, symmetry, and the speed of distributed information propagation.
  • Matrix Algebra as a Tool: The problem is elegantly reframed in terms of matrix properties (eigenvalues, minimal polynomial, kernel). This abstract mathematical framework provides a powerful lens for analyzing and proving results about consensus algorithms.
  • The "Consensus Number" Concept: Introducing the consensus number provides a new metric for characterizing a graph's suitability for fast distributed consensus, moving beyond the simpler diameter measure.

Key Results

  • Counterexample to Definitive Consensus Conjecture: The graph Gcx, with diameter 2, is shown to require more than 2 steps for average consensus using linear protocols. This is the first improvement on the diameter lower bound for linear consensus protocols.
  • Conditions for Consensus: Theorem 3 provides specific algebraic conditions on a matrix $M$ that, if satisfied, guarantee the existence of $D$ compliant matrices for consensus.
  • Distance-Regular Graphs Satisfy Conjecture: Proposition 7 proves that for any distance-regular graph, the definitive consensus conjecture holds. This implies that graphs with significant symmetry automatically satisfy the conjecture.
  • Consensus Number Upper Bounds: Corollary 8 shows that the consensus number of a graph is upper-bounded by $s-1$, where $s$ is the number of distinct eigenvalues of a specific symmetric irreducible nonnegative matrix associated with the graph.

Limitations and Future Work

  • Computational Intractability: The paper notes that solving the large systems of polynomial equations for consensus can be computationally intractable, especially for larger graphs, and mentions that Gröbner basis theory, while a formal method, has exponential time complexity.
  • Open Question on Consensus Number Computability: It remains an open question whether the consensus number of a graph can be efficiently computed or if it can be linked to other known graph invariants.
  • Decentralized Adaptation: While the paper focuses on design-time matrix selection, it acknowledges that when nodes have sufficient memory and computing power, decentralized methods could be adapted to allow nodes to adjust their weights for future consensus iterations.
  • Generalization to Digraphs: The paper primarily focuses on undirected graphs but mentions that some results can be extended to digraphs, suggesting this as a potential area for further research.

Summary updated

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.
BibTeX
@misc{hendrickx2012diameter,
  author = {Julien M. Hendrickx and Raphaël M. Jungers and Alexander Olshevsky and Guillaume Vankeerberghen},
  title = {{Diameter, Optimal Consensus, and Graph Eigenvalues}},
  year = {2012},
  eprint = {1211.6324},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.6324},
}
Figure