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

• Benjamin Doerr (Professeur, LIX, Ecole Polytechnique)
• Pierre Fraigniaud (Directeur de Recherche CNRS), IRIF, Université de Paris
• Mikaël Rabie (Maitre de Conférence), IRIF, Université de Paris

Distributed Computing is dedicated to the design and analysis of algorithms performed by a set of autonomous computing entities (called processes) whose objective is the realization of a common task, in absence of any coordinator.

At a practical level, the general framework of distributed computing is related to very many application domains, including networking (e.g., Internet, P2P systems, social networks, wireless networks, mobile networks, etc.), and multi-processors (e.g., multicore architectures, computational grids, etc.). In fact, distributed computing also finds various kinds of applications outside the technological frameworks, including in particular the study of different distributed and/or dynamic systems as they appear in sociology, physics or in biology (e.g., social networks, insect colonies, school of fish, etc.).

At a fundamental level, distributed computing faces obstacles to efficient computation that are of a nature very different from the ones in classical sequential computing. Indeed, distributed computing has to cope with uncertainty essentially caused by two issues: temporal issues (asynchrony coupled with process failures) and spatial issues (a process is not aware of the states of far away processes in a network). The course 2.18.1 is dedicated to the design and analysis of efficient algorithms coping with spatial constraints. (Instead, the course 2.18.2 is focussing on temporal constraints).

The course will be decomposed into three successive parts:

• Part 1: Fundaments of local computing in networks: solving graph problems locally;
• Part 2: Distributed graph algorithms under communication constraints;
• Part 3: Analysis of information spreading in networks;

• 2.18.2 Distributed algorithms for Shared Memory
• 2.11.1 Advanced algorithms (randomized, online, approximation, etc.)
• 2.29.1 Graph algorithms
• 2.33.1 Computation theory

• Partial Exam: Dec 3, 2020, 9h-12h.
• Final Exam: TBA.

Rules for the partial and final exams:

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

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

Lecture notes and/or slides for Part 1 of the course (lectures 1-8)

Lecture notes and/or slides for Part 2 of the course (lectures 9-12)

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)

• Carole Delporte (Professeur, IRIF, Université de Paris)
• Benjamin Doerr (Professeur, LIX, Ecole Polytechnique)
• Hugues Fauconnier (Professeur, IRIF, Université de Paris)
• Pierre Fraigniaud (Directeur de Recherche CNRS, IRIF, Université de Paris)
• Amos Korman (Directeur de Recherche CNRS, IRIF, Université de Paris)
• Mikaël Rabie (Maitre de Conférence), IRIF, Université de Paris
• Laurent Viennot (Directeur de Recherche INRIA, IRIF, Université de Paris)