2015 • Conference Paper
Reachability of Consensus and Synchronizing Automata
Authors:
Chevalier, Pierre-Yves,
Hendrickx, Julien ,
Jungers, Raphaël M.
Published in:
CDC 2015
We consider the problem of determining the existence of a sequence of matrices driving a discrete-time multi-agent consensus system to consensus. We transform this problem into the problem of the existence of a product of the (stochastic) transition matrices that has a positive column. This allows us to make use of results from automata theory to sets of stochastic matrices. Our main result is a polynomial-time algorithm to decide the existence of a sequence of matrices achieving consensus.