Efficient algorithms for the consensus decision problem
From MaRDI portal
Statistical decision theory (62C99) Complexity and performance of numerical algorithms (65Y20) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30) Stability of control systems (93D99) Stochastic systems in control theory (general) (93E03)
Abstract: We address the problem of determining if a discrete time switched consensus system converges for any switching sequence and that of determining if it converges for at least one switching sequence. For these two problems, we provide necessary and sufficient conditions that can be checked in singly exponential time. As a side result, we prove the existence of a polynomial time algorithm for the first problem when the system switches between only two subsystems whose corresponding graphs are undirected, a problem that had been suggested to be NP-hard by Blondel and Olshevsky.
Recommendations
- How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard
- Two consensus problems for discrete-time multi-agent systems with switching network topology
- Consensus of switched multi-agent systems with random networks
- A unifying convex analysis and switching system approach to consensus with undirected communication graphs
- Signed consensus problems on networks of agents with fixed and switching topologies
Cites work
- Belief Consensus and Distributed Hypothesis Testing in Sensor Networks
- Coherence in Large-Scale Networks: Dimension-Dependent Limitations of Local Feedback
- Consensus and Cooperation in Networked Multi-Agent Systems
- Convergence of Type-Symmetric and Cut-Balanced Consensus Seeking Systems
- Coordination of groups of mobile autonomous agents using nearest neighbor rules
- Distributed average consensus with least-mean-square deviation
- Distributed Subgradient Methods for Multi-Agent Optimization
- Efficient algorithms for the consensus decision problem
- Graph theoretic methods in multiagent networks
- How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 758785 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- Lyapunov indicator of discrete inclusions. I
- On Krause's Multi-Agent Consensus Model With State-Dependent Connectivity
- Stability analysis of switched systems using variational principles: An introduction
- Stability Criteria for Switched and Hybrid Systems
- Switching in systems and control
- The finiteness conjecture for the generalized spectral radius of a set of matrices
- The Lyapunov indicator of discrete inclusions. II
- The Lyapunov indicator of discrete inclusions. III
- Topological sorting of large networks
Cited in
(13)- MinMax algorithms for stabilizing consensus
- Analytic methods for reachability problems
- On the \(m\)-dimensional Cayley-Hamilton theorem and its application to an algebraic decision problem inferred from the \(\mathcal{H}_2\) norm analysis of delay systems
- Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability
- Tight bound for deciding convergence of consensus systems
- Efficient algorithms for the consensus decision problem
- Surface dimension, tiles, and synchronizing automata
- Probabilistic consensus via polling and majority rules
- SECOND-ORDER ITERATIVE METHOD FOR OPTIMAL CONTROL PROBLEMS OF MULTISTAGE PROCESSES
- How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard
- Subspace confinement for switched linear systems
- Fast Algorithms for Geometric Consensuses
- Distributed estimation algorithms on undirected chained graphs with explicit characterization of consensus
This page was built for publication: Efficient algorithms for the consensus decision problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949988)
