Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Three complementary approaches to averaging in decentralized systems

We consider systems of n agents each holding an initial value, and analyze how they can compute the average of these values in a decentralized way, i.e. by local interactions between peers. This issue is central in decentralized systems, as it captures most of the difficulties faced in decentralized computation and control. Averaging algorithms are moreover the basis on which are built many more evolved algorithms. We present three recent results approaching decentralized averaging from complementary angles. First, we show a new symmetry-based convergence condition for consensus-seeking continuous-time dynamical systems. Second, we consider stochastic systems computing the average on expectation, and expose a trade-off leading to new general bounds on the variance of their results, and allowing showing the asymptotic accuracy of large classes of protocols. Finally, we analyze the general problem of computing functions in a network of anonymous finite state automata, and present a multi-purpose algorithm relying on averaging, and requiring O(n^2) computation rounds.

Type of Seminar:
Lecture Series on Directions in Systems and Control
Prof. Julien Hendrickx
Institute of Information and Communication Technologies, Université catholique de Louvain, Louvain-la-Neuve, Belgium
Dec 01, 2011   17:15

ETZ E8, Gloriastrasse 35
Contact Person:

John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
Julien M. Hendrickx is assistant professor (chargé de cours) at the Université catholique de Louvain at the Ecole Polytechnique de Louvain since 2010 and is member of the Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM). He received an engineering degree in applied mathematics and a PhD in mathematical engineering from the Université catholique de Louvain, Belgium, in 2004 and 2008, respectively. He was a visiting researcher at the University of Illinois at Urbana Champaign in 2003-2004, at the National ICT Australia in 2005 and 2006, and at the Massachusetts Institute of Technology in 2006 and 2008. He was a postdoctoral fellow at the Laboratory for Information and Decision Systems of the Massachusetts Institute of Technology 2009 and 2010, holding postdoctoral fellowships of the F.R.S.-FNRS (Fund for Scientific Research) and of Belgian American Education Foundation. Julien Hendrickx is the recipient of the 2008 EECI award for the best PhD thesis in Europe in the field of Embedded and Networked Control, and of the Alcatel-Lucent-Bell 2009 award for a PhD thesis on original new concepts or application in the domain of information or communication technologies.