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é Paris Diderot)

Lecturers Year 2019-2020

Scientific and pedagogical content

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;
Courses in direct connection with this course

Exams

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

Prequisite

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

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)

Pedagogical team

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