Distributed Algorithms and Network Systems

Federica GARIN ( )

Objectives

Distributed algorithms aim at obtaining a global goal by exploiting a large number of simple devices (``agents''), and their local interactions. These algorithms can be for the purposes of estimation in a wireless sensor network, or control e.g. of a self-organized robotic fleet. This introductory class will first review the necessary tools from graph theory and Markov chains, and then present consensus: a prototypical example of distributed algorithm, as well as a building block for more complex algorithms. Theory will be accompanied by implementation on a real-world sensor network: FIT/IoT LAB.

Class schedule

  1. Introduction: network systems
  2. Graphs: fundamentals of algebraic graph theory
  3. Markov chains: convergence to invariant measure, Perron-Frobenius theorem
  4. Consensus (time-invariant graph)
  5. Consensus (gossip: randomly varying graph)
  6. Consensus-based algorithms: using consensus as a building block of other algorithms (e.g., localisation from relative measurements, least-squares regression, gradient descent minimization, distributed Kalman filter, counting nodes in an anonymous network)
  7. Labs (3): implementation of distributed algorithms on real sensor network, remotely using FIT/IoT LAB. Programming language: C.

References

  • F. Bullo, J. Cortes, and S. Martinez, Distributed Control of Robotic Networks, Princeton, 2009. Available on-line.
  • M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in Multiagent Networks, Princeton University Press, 2010.
  • D.A. Levin, Y. Peres, and E.L. Wilmer, Markov chains and mixing times, American Mathematical Society, 2010.
  • F. Garin, L. Schenato, A survey on distributed estimation and control applications using linear consensus algorithms, in "Networked Control Systems", A. Bemporad, M. Heemels, M. Johansson eds, Springer Lecture Notes in Control and Information Sciences, vol. 406, Chapter 3, pp. 75-107, Springer, 2011.

Grading Policy

  • Final Exam: 2/3
  • Labs: 1/3

Handouts

Restricted access area