Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Course 2.18.1: Distributed Algorithms for Networks (24h, 3ECTS)

Responsible of the course: Pierre Fraigniaud (Directeur de Recherche CNRS, IRIF, Université de Paris)

Schedule: Unless specified otherwise, during the first period (Sept. 13 to Nov. 19), the lectures will take place from 10:15 to 11:45 every Tuesday morning, room 1002.

Lecturers Year 2021-2022

Scientific and pedagogical content

Distributed Computing is dedicated to the design and analysis of algorithms performed by a set of autonomous computing entities whose objective is the realization of a common task, in absence of any coordinator, like in, e.g., Internet, P2P systems, cloud computing, wireless networks, social networks, insect colonies, school of fish, etc., and any decentralized system in general.

This course focusses on distributed computing in networks, in which the computing entities have to cope with uncertainty caused by spatial constraints.

The design and analysis of distributed algorithms in networks is tightly connected to the following fields: graph theory, deterministic and randomized algorithms, communication complexity, interactive proofs, etc. The course may even provide examples of connections with algebraic topology, zero-knowledge proofs and quantum computing.


This course does not require specific prerequisite, other than basic knowledge in algorithm design and analysis, probability, and graph theory.

Teaching material 2021-2022

Lecture notes and/or slides sessions 1-2, 7-8, and 15 of the course

Slides for sessions 3-6 of the course

Slides for session 9 of the course

Recommended books

David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA (2000)

Leonid Barenboim, Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, Morgan and Claypool Publishers (2013)


  • Partial Exam: 30/11/2021, 9h00-12h00 (usual room)
  • Final Exam: 08/03/2022, 9h00-12h00 (usual room)

Rules for the partial and final exams:

  • Allowed:
    • all handwritten notes related to the course,
    • copies of slides, exercises and solutions,
  • Not allowed: electronic devices like computers, tablets, cell-phones, etc.
  • Please bring your own A4 size paper.

Pedagogical team

Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA