Performance of linear average-consensus algorithm in large-scale networks

Abstract:

A popular topic in the control-theory community is distributed estimation and control, for sensor and actuator networks deployed on large spatially distributed systems, and for the coordination of multiple autonomous robots or vehicles. A lot of attention has been devoted to linear average-consensus, a very simple linear dynamical system where the state-update matrix is stochastic and satisfies some sparsity constraint. It is both a simple model for coordinated dynamics (also used to model animal flocking behavior, and in studying opinion dynamics in social networks), and a simple algorithm for computing averages in a distributed way (by exchanges of messages with neighbors) which can be used as a building block for more complicated distributed estimation or optimization tasks. I will recall how the convergence analysis of this iterative algorithm can be done by using well-known results from Markov Chains theory (Perron-Frobenius theorem) and from spectral graph theory (spectral gap of the Laplacian matrix for families of graphs). Then, I will show that the definition of different performance measures, more specific to control or estimation problems, leads to analyze other properties of Markov chains and graphs, which depend on all the eigenvalues of the Laplacian matrix instead of on the spectral gap only (e.g., the average first hitting time). I will present results on the asymptotic scaling of some of such costs when the size of the graph tends to infinity, for some families of graphs, in particular 'geometric' graphs.

Presentation Slides

Biography:Federica Garin is junior researcher in the NeCS (Networked Control Systems) team at INRIA Rhône-Alpes, Grenoble, France. She received her B.Sc., MS, and Ph.D. degrees in Applied Mathematics from Politecnico di Torino (Italy) in 2002, 2004, and 2008, respectively. In 2006–2007 she was a visiting scholar at CMRR, University of California at San Diego. In 2008 and 2009 she was a post-doctoral researcher at DEI, Università di Padova (Italy). Her research interests are in the areas of sensor networks, networked control, and infomation and coding theory; she is currently working on distributed and collaborative algorithms for estimation, fault detection and source localization.