How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard

DOI10.1137/12086594XMaRDI QIDQ5173258zbMATH OpenOpenAlexFDO

Authors Vincent D. Blondel, Alex Olshevsky

Publication date 9 February 2015

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.3167

zbMATH Keywords

computational complexityconsensusswitched systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decentralized systems (93A14) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Abstract: A set of stochastic matrices $calP$ is a consensus set if for every sequence of matrices $P(1),P(2),ldots$ whose elements belong to $calP$ and every initial state $x(0)$, the sequence of states defined by $x(t)=P(t)P(t-1)cdotsP(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.

Recommendations

• Efficient algorithms for the consensus decision problem
• Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
• Tight bound for deciding convergence of consensus systems
• Reaching a consensus: a discrete nonlinear time-varying case
• Protocols forcing consensus

Cited in

(7)

• Gossip over holonomic graphs
• Random asynchronous iterations in distributed coordination algorithms
• Tight bound for deciding convergence of consensus systems
• Efficient algorithms for the consensus decision problem
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Phase transitions in the Ising model on a hierarchical random graph based on the triangle
• On primitivity of sets of matrices

This page was built for publication: How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5173258)