Distributed algorithms for networks (2024-2025)
General information
- This is the webpage for the 2024-2025 iteration of the course
Distributed algorithms of networks (C14), taught in the
Master 2 program
of ENS Lyon.
- Last year's webpage is here.
- This year the lecturers are:
Stephan Thomassé,
Laurent Feuilloley, and
Théo Pierron.
(Nicolas Bousquet participated in the design of the course but is
not teaching this year.)
- The time slots are the follwing: Monday 15:45-17:45 and
Friday 10:15-12:15.
- The final grade will be a weighted average of the grade for
scribe notes and the grade for final exam.
Tentative program
Monday November 18 (S. Thomassé)
- Introduction of the LOCAL model and coloring.
Friday November 22 (S. Thomassé)
Monday November 25 (S. Thomassé)
Friday November 29 (S. Thomassé)
Monday December 2 (S. Thomassé)
Friday December 6 (L. Feuilloley)
- Low-diameter network decompositions: locally checkable labelings,
SLOCAL model, basic decomposition, idea of more involved decompositions.
Monday December 9 (L. Feuilloley)
- Derandomization: via low-diameter decompositions, exponential
upper bound on the randomization gap, randomized sinkless orientation
Friday December 13 (T. Pierron)
- Introduction to the CONGEST model
Monday December 16 (L. Feuilloley)
- Round elimination technique for lower bounds
Friday December 20 (L. Feuilloley)
- LCL classifications and gaps
Monday January 6 (L. Feuilloley)
- Efficient algorithms via rounding fractional solutions
Friday January 10 (T. Pierron)
Monday January 13 (T. Pierron)
Friday January 17 (T. Pierron)
Monday January 20 (T. Pierron)
Monday January 24 and 27: No class (except if stated otherwise later.)
Friday January 31: Exam
Useful material