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

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.

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.

Lectures

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