Algorithms and Complexity

(Theory of) Distributed Systems
Graduate Course - Summer Term 2020
Fabian Kuhn


Course description

The course provides an introduction to the fundamentals of distributed systems and algorithms. The course will in particular cover the following topics:

  • distributed systems models
  • time and global states in distributed systems
  • sychronous and asynchronous systems
  • fault tolerance
  • basic distributed algorithms for coordination and agreement tasks
  • basic distributed network algorithms
  • distributed and parallel graph algorithms
  • impossibility results and lower bounds

Lectures and Exercises

  • Lecture: Monday 14:15 - 16:00
  • Exercise Tutorial: Wednesday 12:15 - 14:00

The course consists of 12 weekly 2-hour lectures and there will be 11 or 12 weekly exercise sheets. Lectures and exercise tutorials will be held online by using the video conferencing system zoom. The link on how to access the zoom meetings is available on the lecture online access information page, which is only visible from within the university network (i.e., use VPN to access the page from home). The online lectures will be recorded. The recordings will be available on the same page. To discuss questions and other issues related to the course, we have also created a slack channel for the course. Details are also on the lecture online access information page.

The first lecture will be on Monday, May 11 (at 14:15), the first exercise tutorial will be Wednesday, May 20 (at 12:15). In the first week, we will use the slot on Wednesday, May 13 at 12:15 for a short question and answer session. The last lecture of the course will be on Monday, July 27 and the last exercise tutorial on Wednesday, July 29.

Lecture Material

All material regarding the lecture (literature, slides, recordings, etc.) are available on the

    lecture materials web page

of the course. In order to limit access to this material, this page is only visible from within the university network (i.e., use VPN to access the page from home).

Exercise Sheets

If you want feedback to your solutions, you can submit them either to alkida.balliu at cs.uni-freiburg.de or dennis.olivetti at cs.uni-freiburg.de.

Week Assigned Date Due Date Exercises Sample Solution
1 11.05.2020 17.05.2020 Exercise 01
2 18.05.2020 24.05.2020 Exercise 02
3 25.05.2020 31.05.2020 Exercise 03
4 2.06.2020 7.06.2020 Exercise 04
5 8.06.2020 14.06.2020 Exercise 05
6 15.06.2020 21.06.2020 Exercise 06
7 22.06.2020 28.06.2020 Exercise 07
8 29.06.2020 05.07.2020 Exercise 08
9 06.07.2020 12.07.2020 Exercise 09
10 13.07.2020 19.07.2020 Exercise 10
11 20.07.2020 26.07.2020 Exercise 11
12 27.07.2020 02.08.2020 Exercise 12


Some of the content is for example covered by the following books:

Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6

Distributed Computing: A Locality-Sensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8

Additional literature for each chapter will be provided where available.