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