Objectives:
Distributed systems are composed of several computational units, classically called processes, that run concurrently and independently, without any central control. Additional difficulties are introduced by asynchrony (processes and channels operate at different speeds) and by limited local knowledge (each process has only a local view of the system and has a limited amount of information).
Distributed algorithms are algorithms designed to run in this quite challenging setting. They arise in a wide range of applications, including telecommunications, internet, peer-to-peer computing, blockchain technology...
This course aims at giving a comprehensive introduction to the field of distributed algorithms. A collection of significant algorithms will be presented for asynchronous networked systems, with a particular emphasis on their correctness proofs. Algorithms will be analyzed according to various measures of interest (eg., time and space complexities, communication costs). We will also present some "negative" results, i.e., impossibility theorems and lower bounds as they play a useful role for a system designer to determine what problems are solvable and at what cost.
Content:
- Modelling of distributed networked systems
- Wave and traversal algorithms
- Leader election
- Logical time and global snapshots
- Detection of stable properties
- Synchronizers
- Link reversal algorithms
Language:
The course material is in English. Lectures can be taught either in French or in English, at the students' convenience.
Evaluation:
Graded lab session + final written exam.
Prerequisites:
A fair knowledge of combinatorics and graph theory and is desirable as well as some knowledge of sequential algorithms (INF421).