Theory of Distributed Systems

Advanced Course, 2+2

Basic Information

Lectures:Tuesday, 10:10 - 11:55, E1.4 024 (initially: E1.5 029)
Lecturer:Christoph Lenzen
First lecture:23.10.2018
Tutorials:Friday, 10:10 - 11:50, E1.4 023 (changed!  once: E1.4 021)
Assistant:Ben Wiederhake
First tutorial:26.10.2018
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)

Date, VideoTopic, RoomExerciseDue
23.10., VidColoringE 1.5, room 029Sheet 130.10., 10:10
30.10., VidSynchronizersE 1.5, room 029Sheet 206.11., 10:10
06.11., VidImpossibility of ConsensusE 1.4, room 024Sheet 313.11., 10:10
13.11., VidConsensusE 1.4, room 024Sheet 420.11., 10:10
20.11., VidMaximal Independent Setetc.Sheet 527.11., 10:10
27.11., VidMinimum Spanning TreeSheet 604.12., 10:10
04.12., VidHardness of MSTSheet 711.12., 10:10
11.12., VidRoutingSheet 818.12., 10:10.
18.12., VidSelf-StabilizationSheet 908.01.2019, 10:10
 — (Christmas Break)n/a 
08.01., VidMutEx + S&CSheet 1015.01., 10:10
15.01., VidShared CountersSheet 1122.01., 10:10
22.01., VidGuest lecture "Link Reversal Algorithms" (Matthias Függer)n/a 
29.01. see belowPort NumberingSheet 12optional: 05.02.
05.02., VidGuest lecture "Using Computers to Design Distributed Algorithms" (Jukka Suomela)n/a 
12.&13.02., VidExamn/a 

Regarding the video of lecture 12, "Port Numbering": It seems we encountered some unforeseen hardware issues.  The video feed is horribly bad, so I don't want to make only the video available, but also the audio-only version (aac, ogg, mp3).  The IST already knows about this and will try to fix this until next time.

Schedule (tutorials)

DateTopic, Room (usually E 1.4, room 023)Discussed
26.10.Introduction, Preliminaries 
02.11.ColoringSheet 1
09.11.Synchronizers (reminder: E 1.4, room 023)Sheet 2
16.11.Impossibility of ConsensusSheet 3
23.11.ConsensusSheet 4
30.11.Maximal Independent SetSheet 5
07.12.Minimum Spanning TreeSheet 6
14.12.Hardness of MSTSheet 7
21.12.RoutingSheet 8
04.01.— (Nothing!)n/a
11.01.Self-StabilizationSheet 9
18.01.MutEx + S&C – E 1.4, room 021Sheet 10
25.01.(Talking about the evaluation)n/a
01.02.Shared CountersSheet 11
08.02.Q & A session; then Port NumberingSheet 12


  • Read and believe how we would like to run this course. (Updated 05.11. regarding hand-in time)
  • Subscription to our mailing list 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.