Theory of Distributed Systems

Advanced Course, 2+2

Basic Information

Lectures:Tuesday, 16:00 - 18:00, E1.4 024
Lecturer:Christoph Lenzen
First lecture:22.10.2019
Tutorials:Thursday, 12:00 - 14:00, E1.4 023
Assistant:Johannes Bund
First tutorial:31.10.2019
Prerequisites:No prerequisites beyond basic familiarity with mathematical reasoning are required; prior knowledge on asymptotic notation and (occasionally) standard probabilistic notions can be useful, but is not essential for following the course.



This course offers a broad introduction to the theory underlying distributed systems. Among others, it covers message passing and shared memory, synchrony vs. asynchrony, fault-tolerance, and congestion. The focus lies on key concepts, algorithmic ideas, and mathematical analysis. Despite some overlap in topics, the angle is very different from that of the core lecture distributed systems; in particular, programming is not part of the curriculum.


Theory in the area of distributed computing aims at understanding systems in which limits on communication and lack of coordination or common knowledge are the principal challenges. Moreover, the redundancy provided by multiple agents (be these computers, ants, smartphones, or humans) enables to overcome faults. Uncertainty is faced on many fronts: How large is the network? Is information up-to-date? Does it merely take a long time until a response from a process is received, or did the process fail? We will examine how such issues affect which problems can be solved and at which cost. On the way, surprising and elegant algorithms will surface alongside the principles guiding their design.

Schedule (lectures)

22.10Choose Your AdventurePreliminary meeting (guest: Will Rosenbaum)
29.10ToDS_01Vertex ColoringSheet_0105.11
12.11ToDS_03Impossibility of ConsensusSheet_0319.11
19.11ToDS_04Reaching ConsensusSheet_0426.11
26.11ToDS_05Maximal Independent SetSheet_0503.12
03.12ToDS_06Minimum Spanning TreesSheet_0610.12
10.12ToDS_07Hardness of MST ConstructionSheet_0707.01
17.12Distributed Computing in Bacteria (guest: Matthias Függer)
24.12(Christmas Break)
31.12(Christmas Break)
07.01ToDS_08Distance Approximation and RoutingSheet_0814.01
14.01ToDS_09Self-Stabilization and RecoverySheet_0921.01
21.01ToDS_10Mutual Exclusion and Store & CollectSheet_1028.01
28.01ToDS_11Shared CountersSheet_1104.02
04.02ToDS_12The Port Numbering ModelSheet_12

Schedule (tutorials)

31.10Vertex Coloringprevious lecture, upcoming exercises
07.11Synchronizationprevious lecture, exercise sheet 01
14.11Impossibility of Consensusprevious lecture, exercise sheet 02
21.11Reaching Consensusprevious lecture, exercise sheet 03, upcoming exercises
28.11Maximal Independent Setprevious lecture, exercise sheet 04, upcoming exercises
05.12Minimum Spanning Treesprevious lecture, exercise sheet 05
12.12Hardness of MST Constructionprevious lecture, exercise sheet 06
26.12(Christmas Break)
02.01(Christmas Break)
09.01Distance Approximation and Routingprevious lecture, exercise sheet 07
16.01Self-Stabilization and Recoveryprevious lecture, exercise sheet 08
23.01Mutual Exclusion and Store & Collectprevious lecture, exercise sheet 09
30.01Shared Countersprevious lecture, exercise sheet 10
06.02The Port Numbering Model 


  • Research shows that students perform better on average when they are actively involved in the learning process. Some of you may know this as 'flipped classroom', where students prepare the material on their own and they are offered a discussion session to clarify open questions. We would like to implement some of the ideas into our teaching strategies. However, we will not dictate how this course is going to run. In the spirit of flipped classroom we will have a preliminary meeting where we present the ideas behind it and possibilities we can offer. Afterwards we discuss with students how they would like to run this course. We provide further readings for inverted classroom in the material section.
  • Subscription to our mailing list (tods1920) is mandatory and has two purposes: (1) We will use it to distribute material and information, and we will assume that everyone in the course received them. (2) Please use the list to discuss the lecture, exchange material, clarify questions, etc.; just please don't post solutions to the exercises.