How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-Hard

Vincent D. Blondel, Alex OlshevskySIAM J. Control and Optimization 2014 · OpenReview

TL;DR

This paper introduces a novel "avoiding sets condition" that precisely characterizes when a set of stochastic matrices guarantees consensus in distributed systems. This condition not only provides a clear theoretical framework but also proves that consensus is decidable, though it's NP-hard to determine in polynomial time, even for just two matrices.

What Problem Does This Paper Address?

In distributed systems, such as swarms of robots or sensor networks, agents often need to agree on a common value or state. This agreement, known as consensus, is typically achieved through iterative updates governed by stochastic matrices. A key challenge in designing these systems is finding reliable conditions that guarantee consensus, especially when the communication structure (and thus the matrices) can change over time. While many sufficient conditions exist, a general, combinatorial necessary and sufficient condition has been elusive. Furthermore, understanding the computational complexity of verifying consensus has been an open question. This paper aims to bridge this gap by providing a definitive combinatorial condition for consensus and analyzing its computational complexity.

Methods

The core of this paper is the introduction and proof of the "avoiding sets condition." This condition states that a set of stochastic matrices is a consensus set if and only if there do not exist two specific sequences of sets and matrices that "avoid" each other. The paper rigorously proves this condition is both necessary and sufficient. To establish decidability, the authors show that checking this condition, while potentially computationally intensive, can be done algorithmically. The NP-hardness result is demonstrated by constructing a reduction from the 3-SAT problem to the consensus problem, showing that if consensus could be decided in polynomial time, then 3-SAT could also be solved in polynomial time, which is widely believed to be false.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Avoiding Sets Condition": This is the central contribution. It provides a concrete, combinatorial way to determine if a set of matrices will lead to consensus, moving beyond abstract properties of matrix products.
  • Decidability of Consensus: The paper proves that determining if a set of matrices is a consensus set is algorithmically decidable. This is a significant theoretical result, as it means a definitive answer can always be found.
  • Inherent Computational Difficulty: Despite being decidable, the paper establishes that checking consensus is NP-hard. This implies that for large or complex systems, finding a consensus-guaranteeing configuration might be computationally intractable in the worst case.
  • Connection to Graph Theory: The "avoiding sets condition" has a strong interpretation in terms of graph theory, relating to the existence of disjoint "set cycles" in sequences of directed graphs derived from the matrices.

Key Results

  • Theorem 2.2: A compact set of stochastic matrices is a consensus set if and only if the "avoiding sets condition" holds. This condition involves the non-existence of two specific sequences of sets and matrices that avoid each other.
  • Decidability: The paper shows that the problem of determining if a finite set of stochastic matrices is a consensus set is decidable.
  • NP-Hardness (Directed Matrices): Determining if a set of two stochastic matrices is a consensus set is NP-hard (unless P=NP).
  • NP-Hardness (Undirected Matrices): Determining if a set of three undirected stochastic matrices is a consensus set is NP-hard (unless P=NP).

Limitations and Future Work

The paper acknowledges that while the "avoiding sets condition" is decidable, its direct verification can be computationally expensive, potentially requiring more than polynomial time. The authors also note that their NP-hardness results for undirected matrices are for three or more matrices, and they believe a similar result might hold for two undirected matrices but have not proven it. Future work could explore more efficient algorithms for checking the avoiding sets condition, investigate the complexity for smaller numbers of undirected matrices, and explore the decidability and complexity of consensus problems for other important subclasses of switched systems.

Summary updated

Abstract

A set of stochastic matrices ${\cal P}$ is a consensus set if for every sequence of matrices $P(1), P(2), \ldots$ whose elements belong to ${\cal P}$ and every initial state $x(0)$, the sequence of states defined by $x(t) = P(t) P(t-1) \cdots P(1) x(0)$ converges to a vector whose entries are all identical. In this paper, we introduce an “avoiding set condition” for compact sets of matrices and prove in our main theorem that this explicit combinatorial condition is both necessary and sufficient for consensus. We show that several of the conditions for consensus proposed in the literature can be directly derived from the avoiding set condition. The avoiding set condition is easy to check with an elementary algorithm, and so our result also establishes that consensus is algorithmically decidable. Direct verification of the avoiding set condition may require more than a polynomial time number of operations. This is, however, likely to be the case for any consensus checking algorithm since we also prove in this paper that unless $P=NP$, consensus cannot be decided in polynomial time.
BibTeX
@article{blondel2014how,
  author = {Vincent D. Blondel and Alex Olshevsky},
  title = {{How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-Hard}},
  journal = {SIAM J. Control and Optimization},
  year = {2014},
  url = {https://openreview.net/forum?id=DL39xyrolmg},
}

Loading related content...

Figure