Theory of Distributed Systems

Advanced Course, 2+2

Basic Information

Lectures:Monday, 12:15 - 14:00, E1.4 023
Lecturer:Christoph Lenzen
First lecture:26. October 2015
Tutorials:Tuesday, 12:15 - 14:00, E1.4 023
Assistant:Stephan Friedrichs
First tutorial:TBA
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.


Distributed Coloring Algorithm

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.


DateTopicExercise SheetExercise Due
26.10.2015ColoringSheet 102.11.2015, 14:00
02.11.2015SynchronizersSheet 209.11.2015, 14:00
09.11.2015Impossibility of ConsensusSheet 316.11.2015, 14:00
16.11.2015Reaching ConsensusSheet 423.11.2015, 14:00
23.11.2015Maximal Independent SetSheet 530.11.2015, 14:00
30.11.2015Minimum Spanning TreesSheet 607.12.2015, 14:00
07.12.2015Hardness of MST ConstructionSheet 714.12.2015, 14:00
14.12.2015Distance Approximation and Routing*Sheet 804.01.2016, 14:00
21.12.2015Christmas Break
28.12.2015Christmas Breakn/an/a
04.01.2016Self-Stabilization and RecoverySheet 911.01.2016, 14:00
11.01.2016Mutual Exclusion and Store & CollectSheet 1018.01.2016, 14:00
18.01.2016Shared CountersSheet 1125.01.2016, 14:00
25.01.2016The Port Numbering Model*Sheet 1201.02.2016, 14:00
01.02.2016Summary and Questionsn/an/a

*) Section 8.5 (Weighted APSP) and Lecture 12 (Port Numbering) are not relevant for the exam


  • Read and believe how we would like to run this course.
  • 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.
  • Oral exams will be held on Monday, 15.02.2016 at individually assigned timeslots.
  • We'll use the last TA session (09.02.2016) for Q&A. Please prepare questions (if you hand them in early I have chance to prepare answers).