title:
Distributed Algorithms for Networks
Algorithmique distribuée pour les réseaux
manager:
Pierre Fraigniaud
ects:
3
period:
1-2
hours:
24
weeks:
16
hours-per-week:
1.5
language:
1/2 French by default 1/2 English
lang:
track:
A
themes:
Parallel/Distributed Algo.
order:
2.18.1
successor:
disc
link:
view
  • [2.18.1]
  • Distributed Algorithms for Networks
    Algorithmique distribuée pour les réseaux
  • Language:
  • Period:
  • 1-2.
  • Duration:
  • 24h (1.5h/week).
  • ECTS:
  • 3.
  • Manager:
  • Pierre Fraigniaud.

Schedule: Unless specified otherwise, during the period from Sept. 19, 2024, to Feb. 27, 2025, the lectures will take place from 10:30 to 12:00 every Thursday morning, room 1002 of Building Sophie Germain (Université Paris Cité).

Lecturers Year 2024-2025

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 typical problems to be solved in this context are graph problems, such as coloring, construction of a maximal independent set (MIS), construction of a minimum-weight spanning tree (MST), etc.

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.

Prequisite

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

Teaching material 2024-2025

Below are links to teaching material from 2024-2025, and previous years. The slides of the 2024-2025 lectures will be posted online.

Lecture notes and slides MPRI P. Fraigniaud

Slides MPRI M. Rabie

Slides MPRI A. Paz

Recommended books

Juho Hirvonen and Jukka Suomela: Distributed Algorithms 2020, Aalto University, Finland

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)

Exams

  • Partial Exam: Thursday, November 28, 2024, 10h30-12h00, room 1002.
  • Final Exam: Thursday, March 6, 2025, 10h30-12h00, room 1002.

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