Finite-time consensus using stochastic matrices with positive diagonals
It provides theoretical limits and possibilities for finite-time consensus in distributed systems, which is important for network coordination and control.
This paper proves that finite-time average consensus is always achievable for connected undirected graphs using linear iterations with stochastic matrices having positive diagonals, while for directed graphs, necessary conditions include strong connectivity and an even-length simple cycle.
We discuss the possibility of reaching consensus in finite time using only linear iterations, with the additional restrictions that the update matrices must be stochastic with positive diagonals and consistent with a given graph structure. We show that finite-time average consensus can always be achieved for connected undirected graphs. For directed graphs, we show some necessary conditions for finite-time consensus, including strong connectivity and the presence of a simple cycle of even length.