Algorithms and Complexity

(Theory of) Distributed Systems
Graduate Course - Summer Term 2021
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


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

Lectures and exercise tutorials will be held online by using the video conferencing system Zoom. Details on how to access the Zoom meetings are found in the technical section below.

For questions and discussions regarding the lecture and the exercises, we use Zulip as a discussion forum. Information on how to get access to our Zulip server can also be found in the technical section below.

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


Below you find the weekly exercise sheet. The submission of exercises is carried out online with the Daphne course management system. All technical details on how to submit your exercise sheet via Daphne is given in the section below. For further inquiries send an email to salwa.faour@cs.uni-freiburg.de or philipp.schneider@cs.uni-freiburg.de

Exercise Assigned Due (12 pm) Solution

Exercise 01 19.04.2021 28.04.2021 Solution 01
Exercise 02 28.04.2021 05.05.2021 Solution 02
Exercise 03 05.05.2021 12.05.2021 Solution 03
Exercise 04 12.05.2021 17.05.2021 Solution 04
Exercise 05 19.05.2021 02.06.2021 Solution 05
Exercise 06 02.06.2021 09.06.2021 Solution 06
Exercise 07 09.06.2021 16.06.2021 Solution 07
Exercise 08 16.06.2021 23.06.2021 Solution 08
Exercise 09 23.06.2021 30.06.2021 Solution 09
Exercise 10 30.06.2021 07.07.2021 Solution 10
Exercise 11 07.07.2021 14.07.2021 Solution 11
Exercise 12 15.06.2021 23.07.2021 Solution 12

Technical Information

Data Access for Zoom and Zulip

The link on how to access the Zoom meetings for both the lectures and exercise tutorials and the information on how to get access to our Zulip server is available here. Note that the information is only visible from within the university network (i.e., use VPN to access the page from home or access the internet via the university eduroam).

Daphne and Subversion (SVN)

The exercises are submitted via Daphne. On Daphne, an overview of the points you achieved so far is given. Exercises are also available there. Please click on this link to register for the course with your rz-account.

After registration, a SVN repository will be created for you with an URL of the following form:


You should do a "checkout" of your SVN-repository (using the URL described above) to get a local copy on your pc. With the command "update" you synchronize your local copy with the current version on the server. Through the command "commit" you upload your local files to your repository on the server. A more detailed overview can be found here. There are different subversion clients you can use. For Windows Tortoise-SVN is recommended.

Note that every solution of an exercise sheet must be uploaded ("committet") to a separate folder named exercise-XY, where XY is the exercise number (with a leading 0 if smaller than 10). This folder will be automatically locked (that is, no commits are possible anymore) after the submission deadline!


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.