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 |
| Credits: | 6 |
| Exam: | 11.02.2020 |
| 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. |
Description
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 | Script | Topic | Exercise | Due |
|---|---|---|---|---|
| 22.10 | Choose Your Adventure | Preliminary meeting (guest: Will Rosenbaum) | — | — |
| 29.10 | ToDS_01 | Vertex Coloring | Sheet_01 | 05.11 |
| 05.11 | ToDS_02 | Synchronizers | Sheet_02 | 12.11 |
| 12.11 | ToDS_03 | Impossibility of Consensus | Sheet_03 | 19.11 |
| 19.11 | ToDS_04 | Reaching Consensus | Sheet_04 | 26.11 |
| 26.11 | ToDS_05 | Maximal Independent Set | Sheet_05 | 03.12 |
| 03.12 | ToDS_06 | Minimum Spanning Trees | Sheet_06 | 10.12 |
| 10.12 | ToDS_07 | Hardness of MST Construction | Sheet_07 | 07.01 |
| 17.12 | — | Distributed Computing in Bacteria (guest: Matthias Függer) | — | — |
| 24.12 | — | (Christmas Break) | — | — |
| 31.12 | — | (Christmas Break) | — | — |
| 07.01 | ToDS_08 | Distance Approximation and Routing | Sheet_08 | 14.01 |
| 14.01 | ToDS_09 | Self-Stabilization and Recovery | Sheet_09 | 21.01 |
| 21.01 | ToDS_10 | Mutual Exclusion and Store & Collect | Sheet_10 | 28.01 |
| 28.01 | ToDS_11 | Shared Counters | Sheet_11 | 04.02 |
| 04.02 | ToDS_12 | The Port Numbering Model | Sheet_12 | — |
Schedule (tutorials)
| Date | Topic | Discussed |
|---|---|---|
| 24.10 | — | — |
| 31.10 | Vertex Coloring | previous lecture, upcoming exercises |
| 07.11 | Synchronization | previous lecture, exercise sheet 01 |
| 14.11 | Impossibility of Consensus | previous lecture, exercise sheet 02 |
| 21.11 | Reaching Consensus | previous lecture, exercise sheet 03, upcoming exercises |
| 28.11 | Maximal Independent Set | previous lecture, exercise sheet 04, upcoming exercises |
| 05.12 | Minimum Spanning Trees | previous lecture, exercise sheet 05 |
| 12.12 | Hardness of MST Construction | previous lecture, exercise sheet 06 |
| 19.12 | — | — |
| 26.12 | (Christmas Break) | — |
| 02.01 | (Christmas Break) | — |
| 09.01 | Distance Approximation and Routing | previous lecture, exercise sheet 07 |
| 16.01 | Self-Stabilization and Recovery | previous lecture, exercise sheet 08 |
| 23.01 | Mutual Exclusion and Store & Collect | previous lecture, exercise sheet 09 |
| 30.01 | Shared Counters | previous lecture, exercise sheet 10 |
| 06.02 | The Port Numbering Model |
Announcements
- 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.
Material
- We combine the lecture scripts for a complete script. (Uploaded 28.01.2020)
- We provide a short script on notation and preliminaries for this course. (Uploaded 9.8.2019)
- You can find information on active learning in the following resources:
- Measuring active learning versus feeling of learning in response to being actively engaged in the classroom
- Active learning increases student performance in science, engineering and mathematics
- How 'Flipping' the Classroom Can Improve the Traditional Lecture
- The Flipped Classroom: A Survey of the Research
- If you are interested in the material you can have a look at a previous iteration of this course