Distributed Computing for networks

Master 2 - ENS Lyon

Lecturers: Nicolas Bousquet, Laurent Feuilloley and Théo Pierron.


General overview of the course

In centralized algorithms, computation can be performed with a full knowledge on the instance. On the contrary, in distributed algorithms, the different nodes of a network should take a decision only with a partial knowledge of the system. The goal is to find the best trade-off detween the quality of the solution determined by the nodes of the network and the quantity of information (as well as the time needed) to find that solution.

The first part of the course will consist in studying the different models of computation for networks (LOCAL, CONGEST, synchronicity vs asynchronicity), their advantages and their limits and how we can evaluate their performances. We will present next the classic algorithms and techniques such as rake and compress, identification compressionn as well as techniques to prove lower bounds on the complexity of these problems (communication complexity...). The last part of the lectures will deal with fault tolerance with a focus on local certification, a research topic that has attrached a lot of attention in the last years.

Prerequisite

Basic knowledge on graphs, algorithms, complexity.

Evaluation

List of articles

The list of articles for January 2024 is available here

Exercices

List of exercices to prepare the exam here.

Sources