Descriptif
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).
Diplôme(s) concerné(s)
- Echanges PEI
- M1 Informatique - Voie Jacques Herbrand - X
- Cybersecurity : Threats and Defenses
- Titre d’Ingénieur diplômé de l’École polytechnique
- Cyber Physical System
- M1 MPRI - Foudations of Computer Science
- M1 Cyber - Cybersecurity
- M1 HPDA - High Performance Data Analytics
- M2 HPDA - High Performance Data Analytics
- M1 PDS - Parallel and Distributed Systems
- M2 PDS - Parallel and Distributed Systems
Parcours de rattachement
- MScT CTD - Semestre 1
- M1 Informatique - Voie Jacques Herbrand - X - Semestre 1
- Conception, Modélisation et Architecture des Systèmes Industriels Complexes - Semestre 1
- M1 MPRI - Foudations of Computer Science - Master 1A
- M1 Cyber - Cybersecurity - Master 1A
- M1 HPDA - High Performance Data Analytics - Master 1A
- M2 HPDA - High Performance Data Analytics - Master 2A
- M1 PDS - Parallel and Distributed Systems - Master 1A
- M2 PDS - Parallel and Distributed Systems - Master 2A
Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme Cybersecurity : Threats and Defenses
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 4 ECTS
Pour les étudiants du diplôme M1 Informatique - Voie Jacques Herbrand - X
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 4 ECTS
Pour les étudiants du diplôme Cyber Physical System
Le rattrapage est autorisé (Note de rattrapage conservée)Pour les étudiants du diplôme M1 PDS - Parallel and Distributed Systems
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 4 ECTS
Pour les étudiants du diplôme M1 HPDA - High Performance Data Analytics
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 4 ECTS
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme M1 MPRI - Foudations of Computer Science
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
Pour les étudiants du diplôme M1 Cyber - Cybersecurity
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 4 ECTS
Pour les étudiants du diplôme M2 PDS - Parallel and Distributed Systems
Le rattrapage est autorisé (Note de rattrapage conservée)Pour les étudiants du diplôme M2 HPDA - High Performance Data Analytics
Le rattrapage est autorisé (Note de rattrapage conservée)Pour les étudiants du diplôme Echanges PEI
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.