On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms

Alexander Olshevsky, John N. TsitsiklisIEEE Trans. Automatic Control 2008 · OpenReview

TL;DR

This paper proves that for a specific class of consensus algorithms used in multi-agent systems, a quadratic Lyapunov function, often used to guarantee convergence, does not exist. This finding is significant because it highlights the limitations of traditional stability analysis for these systems and suggests that alternative methods are needed to understand their convergence behavior and time.

What Problem Does This Paper Address?

In multi-agent systems (like swarms of robots or distributed sensor networks), agents often need to agree on a common value or "opinion." Consensus algorithms are designed to achieve this, where each agent updates its opinion based on information from its neighbors. While these algorithms are known to converge under certain conditions, proving this convergence often relies on finding a Lyapunov function – a mathematical tool that decreases over time as the system approaches its stable state. Quadratic Lyapunov functions are particularly desirable due to their analytical tractability. However, for switched linear systems (where the update rules can change over time, as in dynamic communication networks), the existence of such functions is not guaranteed. This paper specifically investigates whether quadratic Lyapunov functions exist for a common type of consensus algorithm, particularly when the communication topology (who talks to whom) can change.

Methods

The authors tackle this problem by first defining a class of "candidate" quadratic Lyapunov functions (class Q) that possess certain desirable properties, such as being non-negative, having a zero value at the consensus state, and decreasing with each iteration of the algorithm for any valid communication graph. They then construct a specific example of a consensus algorithm and a corresponding set of communication graphs that belong to the "symmetric, equal-neighbor" model. The core of their proof involves showing that for this specific model, no function within class Q can exist when the number of agents is sufficiently large (n ≥ 8). They achieve this by leveraging permutation invariance: if a quadratic form is a Lyapunov function for a system, it should remain so even if the agents' labels are permuted. By summing over all possible permutations, they derive a unique candidate matrix for the quadratic form. They then demonstrate that this candidate function fails to decrease for a specific graph and initial condition, thus proving its non-existence as a Lyapunov function.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and constructing a counterexample rather than empirical evaluation on datasets.

Key Insights and Ideas

  • The "span norm" is not enough: Traditional proofs for consensus convergence often rely on the "span norm" (the difference between the maximum and minimum opinions). While this guarantees convergence, it can lead to overly conservative estimates of convergence time. Quadratic Lyapunov functions offer a path to tighter bounds.
  • Switched systems are tricky: Even though individual linear systems often have quadratic Lyapunov functions, when the system switches between different linear modes (different communication graphs), the existence of a common quadratic Lyapunov function is not guaranteed.
  • Permutation invariance is key: The paper ingeniously uses the fact that the underlying consensus problem is invariant to the labeling of agents. This allows them to construct a unique candidate Lyapunov function by averaging over all possible permutations.
  • A concrete counterexample: The paper provides a specific graph structure and initial condition that demonstrates the failure of the candidate Lyapunov function, proving its non-existence for n ≥ 8. This moves beyond numerical verification to an analytical proof.

Key Results

The main result is the proof that for the symmetric, equal-neighbor consensus model with n ≥ 8 agents, no quadratic Lyapunov function exists that satisfies the basic requirements of decreasing with each iteration for all possible connected graphs. The paper also provides conditions under which quadratic Lyapunov functions do exist, particularly for fixed (non-switched) communication graphs that possess a positive left eigenvector associated with the eigenvalue 1.

Limitations and Future Work

The paper focuses on a specific class of consensus algorithms (symmetric, equal-neighbor) and a specific type of Lyapunov function (quadratic). The authors acknowledge that their result applies to this particular setting and that other types of Lyapunov functions or different algorithm variants might still possess quadratic Lyapunov functions. Future work could explore:

  • Investigating the existence of quadratic Lyapunov functions for other classes of consensus algorithms or communication topologies.
  • Exploring alternative, non-quadratic Lyapunov functions for analyzing the convergence of these systems.
  • Developing tighter convergence time bounds that do not rely on quadratic Lyapunov functions.
  • Extending the analysis to systems with continuous-time dynamics.

Summary updated

Abstract

We provide an example proving that there exists no quadratic Lyapunov function for a certain class of linear agreement/consensus algorithms, a fact that had been numerically verified in . We also briefly discuss sufficient conditions for the existence of such a Lyapunov function.
BibTeX
@article{olshevsky2008nonexistence,
  author = {Alexander Olshevsky and John N. Tsitsiklis},
  title = {{On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms}},
  journal = {IEEE Trans. Automatic Control},
  year = {2008},
  url = {https://openreview.net/forum?id=pHxoJvpIZyI},
}
Figure