|Lecture time:||Tuesday 10:15-12:00|
|Lecture room:||E1 4 023|
|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.
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.