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

• Pierre Fraigniaud (Directeur de Recherche CNRS), LIAFA, Université Paris Diderot
• Benjamin Doerr (Professeur, LIX, Ecole Polytechnique)

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). 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: November 21, 2019, 9h-12h, usual room.
• 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 and in probability.

Lecture notes and slides for Parts 1 and 2

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, LIAFA, Université Paris Diderot)
• Benjamin Doerr (Professeur, LIX, Ecole Polytechnique)
• Hugues Fauconnier (Maitre de Conférences, LIAFA, Université Paris Diderot)
• Pierre Fraigniaud (Directeur de Recherche CNRS, LIAFA, Université Paris Diderot)
• Amos Korman (Chargé de Recherche CNRS, LIAFA, Université Paris Diderot)
• Adrian Kosowski (Chargé de Recherche INRIA, LIAFA, Université Paris Diderot)
• Laurent Viennot (Directeur de Recherche INRIA, LIAFA, Université Paris Diderot)