P4/2019

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

News

Slides and exercises

Literature

- 19.06.2019: Solutions to HW6 are available.
- 12.06.2019: Solutions to HW4 are available.
- 29.05.2019: Solutions to HW3 are available.
- 14.05.2019: Solutions to HW2 are available.
- 25.04.2019: Solutions to HW1 are available.
- The first lecture:
**Wednesday, Apr 17**13h30, Amphi Grenat.

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 |

- M. Herlihy, D. Kozlov, and S. Rajsbaum, "Distributed Computing through Combinatorial Topology", Morgan Kaufman, 2014, ebook on Dawsonera (log in via Shibboleth using your TPT account).
- R. Guerraoui, P. Kuznetsov. Algorithms for Concurrent Systems. Also availavble as ebook.
- M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008, ebook
- N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers. 1996
- H. Attiya, J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Addison Wesley. 2006