Reachability of Consensus and Synchronizing Automata
This work provides a polynomial-time solution for a fundamental problem in consensus systems, which is relevant for control theory and multi-agent systems.
The authors address the problem of determining whether a sequence of stochastic matrices can drive a discrete-time consensus system to consensus, transforming it into a problem of the existence of a product with a positive column. They provide a polynomial-time algorithm to decide this existence.
We consider the problem of determining the existence of a sequence of matrices driving a discrete-time consensus system to consensus. We transform this problem into one of the existence of a product of the transition (stochastic) matrices that has a positive column. We then generalize some results from automata theory to sets of stochastic matrices. We obtain as a main result a polynomial-time algorithm to decide the existence of a sequence of matrices achieving consensus.