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, for example of a self-organized robotic fleet. This introductory class will first review the necessary tools from graph theory 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. Properties of stochastic matrices, 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., least squares regression, calibration, clock synchronization, gradient descent minimization, distributed Kalman filter, counting nodes in an anonymous network)
  7. Labs (3): implementation of distributed algorithms on a real sensor network, remotely using FIT/IoT LAB. Programming language: C.

References

  • F. Bullo, Lectures on Network Systems. Available on-line: webpage, pdf.
  • 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. Available on-line: pdf

Grading Policy

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

Handouts

Restricted access area