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
- Final exam.
- Reading of an article (by groups of 2).
List of articles
The list of articles for January 2024 is available here
Exercices
List of exercices to prepare the exam here.
Sources