max planck institut
mpii logo Minerva of the Max Planck Society

Theory of Distributed Systems (Winter Term 2014/15)

Basic Information

Lecture time: Tuesday 10:15-12:00
Lecture room: E1 4 023
Lecturer: Christoph Lenzen
Teaching Assistant: Cosmina Croitoru
TA sessions: biweekly on Friday, 10:15-12:00 (starting in first lecture week)
TA session room: E1 4 023


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.

Prerequisites, Organization, Grading

This is a 5-credit-point advanced course ("Spezialvorlesung"). 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. If you are interested in attending the course, especially if you will do so for credit, please read this.


The script and exercise sheet for each lecture will appear shortly after the fact. For completeness and possible further study, the script will provide references to the literature. Studying these is entirely optional, as the script is meant to be self-contained.

Date Topic Lecture Script Exercise Sheet Exercises Due
Oct 21 List Coloring Lecture 1 Exercise 1 Oct 28
Oct 28 Synchronizers Lecture 2 Exercise 2 Nov 4
Nov 4 Impossibility of Consensus Lecture 3 Exercise 3 Nov 11
Nov 11 Reaching Consensus Lecture 4 Exercise 4 Nov 18
Nov 18 Maximal Independent Sets Lecture 5 Exercise 5 Nov 25
Nov 25 Minimum Spanning Trees Lecture 6 Exercise 6 Dec 2
Dec 2 Hardness of MST Construction Lecture 7 Exercise 7 Dec 9
Dec 9 Distance Approximation and Routing Lecture 8 Exercise 8 Dec 30
Dec 16 Stabilization and Recovery Lecture 9 Exercise 9 Jan 6
Jan 6 Mutual Exclusion and Store & Collect Lecture 10 Exercise 10 Jan 13
Jan 13 Shared Counters Lecture 11 Exercise 11 Jan 20
Jan 20 Bipartite Matching and Vertex Cover Lecture 12 Exercise 12 Jan 27
Jan 27 Dynamic Networks and Approximate Consensus
(guest lecture by Matthias Fuegger)
N/A prepare Qs for Q&A session Feb 3
Feb 3 Q&A session N/A prepare for exam Feb 10
Feb 10 oral exams N/A N/A N/A

All lectures in a single file.

More Courses of the Algorithms and Complexity Group