v2.11.0 (5757)

PA - C7 - INF571 : Distributed Computing

Domaine > Informatique.

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).

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme M1 Cyber - Cybersecurity

Le rattrapage est autorisé (Note de rattrapage conservée)
    L'UE est acquise si note finale transposée >= C
    • Crédits ECTS acquis : 5 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)
      L'UE est acquise si note finale transposée >= C
      • Crédits ECTS acquis : 5 ECTS

      La note obtenue rentre dans le calcul de votre GPA.

      Pour les étudiants du diplôme Cyber Physical System

      Le rattrapage est autorisé (Note de rattrapage conservée)
        L'UE est acquise si note finale transposée >= C

          Pour les étudiants du diplôme Echanges PEI

          Le rattrapage est autorisé (Note de rattrapage conservée)
            L'UE est acquise si note finale transposée >= C
            • 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)
              L'UE est acquise si note finale transposée >= C
              • 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)
                L'UE est acquise si note finale transposée >= C

                  Pour les étudiants du diplôme M1 Informatique - Voie Jacques Herbrand - X

                  Le rattrapage est autorisé (Note de rattrapage conservée)
                    L'UE est acquise si note finale transposée >= C
                    • Crédits ECTS acquis : 4 ECTS

                    Pour les étudiants du diplôme M1 MPRI - Foudations of Computer Science

                    Pour les étudiants du diplôme Cybersecurity : Threats and Defenses

                    Le rattrapage est autorisé (Note de rattrapage conservée)
                      L'UE est acquise si note finale transposée >= C
                      • Crédits ECTS acquis : 4 ECTS

                      Pour les étudiants du diplôme M2 HPDA - High Performance Data Analytics

                      Le rattrapage est autorisé (Note de rattrapage conservée)
                        L'UE est acquise si note finale transposée >= C

                          Pour les étudiants du diplôme M1 HPDA - High Performance Data Analytics

                          Le rattrapage est autorisé (Note de rattrapage conservée)
                            L'UE est acquise si note finale transposée >= C
                            • Crédits ECTS acquis : 4 ECTS
                            Veuillez patienter