Distributed function calculation and consensus using linear iterative strategies
- 25 April 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 26 (4) , 650-660
Abstract
Given an arbitrary network of interconnected nodes, we develop and analyze a distributed strategy that enables a subset of the nodes to calculate any given function of the node values. Our scheme utilizes 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. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix of the linear iteration, and with outputs for each node that are captured by the set of values that are available to that node at each time-step. In connected networks with time-invariant topologies, we use observability theory to show that after running the linear iteration for a finite number of time-steps with almost any choice of weight matrix, each node obtains enough information to calculate any arbitrary function of the initial node values. The problem of distributed consensus via linear iterations, where all nodes in the network calculate the same function, is treated as a special case of our approach. In particular, our scheme allows nodes in connected networks with time-invariant topologies to reach consensus on any arbitrary function of the initial node values in a finite number of steps for almost any choice of weight matrix.Keywords
This publication has 16 references indexed in Scilit:
- Consensus and Cooperation in Networked Multi-Agent SystemsProceedings of the IEEE, 2007
- Finite-time convergent gradient flows with applications to network consensusAutomatica, 2006
- Discrete-time average-consensus under switching network topologies2006
- A survey of consensus problems in multi-agent coordination2005
- A scheme for robust distributed sensor fusion based on average consensus2005
- Fast linear iterations for distributed averagingSystems & Control Letters, 2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- Matrix Analysis1985
- Determination of generic dimensions of controllable subspaces and its applicationIEEE Transactions on Automatic Control, 1980
- Structural controllabilityIEEE Transactions on Automatic Control, 1974