Finite-Time Distributed Consensus in Graphs with Time-Invariant Topologies
- 1 July 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in American Control Conference (ACC)
- No. 07431619,p. 711-716
Abstract
We present a method for achieving consensus in distributed systems in a finite number of time-steps. Our scheme involves a linear iteration where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. If D denotes the degree of the minimal polynomial of the weight matrix associated with the linear iteration, we show that each node can immediately calculate the consensus value as a linear combination of its own past values over at most D time-steps. We also show that each node can determine the coefficients for this linear combination in a decentralized manner. The proposed scheme has the potential to significantly reduce the time and communication required to reach consensus in distributed systems.Keywords
This publication has 9 references indexed in Scilit:
- Finite-time convergent gradient flows with applications to network consensusAutomatica, 2006
- Convergence in Multiagent Coordination, Consensus, and Flocking2006
- Norm of the inverse of a random matrix2006
- Discrete-time average-consensus under switching network topologies2006
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Fast linear iterations for distributed averagingSystems & Control Letters, 2004
- On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matricesThe Electronic Journal of Linear Algebra, 2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- Matrix Analysis1985