MITRO207 Distributed Computing and Combinatorial Topology


Prof. Petr Kuznetsov, office hours: C213-2, appointment by email
INFRES, Telecom ParisTech


Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Our dependence on performance and reliability of distributed systems becomes more and more imminent. Therefore, understanding fundamentals of distributed computing is of crucial importance.

This course is devoted to the use of combinatorial topology, the approach that has recently been used to close several long-standing open questions in distributed computability. The course is based on the textbook by Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum, "Distributed Computing through Combinatorial Topology".

Slides and exercises


Slides and exercises

Date Class Exercises Solutions
17.04.2019 Introduction HW 1 solutions
24.04.2019 Two-process computations
Seven Königsberg Bridges
HW 2 solutions
15.05.2019 Basics of combinatorial topology HW 3 solutions
29.05.2019 Exercise session Problems
5.06.2019 Colorless tasks HW 4 solutions
12.06.2019 Solving colorless tasks HW 5 solutions
19.06.2019 Read-Write Protocols for General Tasks
19.06.2019 Q&A session
25.06.2019 Exam Annales: see the exercises above