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)

DateScriptTopicExerciseDue
22.10Choose Your AdventurePreliminary meeting (guest: Will Rosenbaum)
29.10ToDS_01Vertex ColoringSheet_0105.11
05.11ToDS_02SynchronizersSheet_0212.11
12.11ToDS_03Impossibility of ConsensusSheet_0319.11
19.11ToDS_04Reaching ConsensusSheet_0426.11
26.11ToDS_05Maximal Independent SetSheet_0503.12
03.12ToDS_06Minimum Spanning TreesSheet_0610.12
10.12ToDS_07Hardness of MST ConstructionSheet_0707.01
17.12Distributed Computing in Bacteria (guest: Matthias Függer)
24.12(Christmas Break)
31.12(Christmas Break)
07.01ToDS_08Distance Approximation and Routing  
14.01 tba  
21.01 tba  
28.01 tba  
04.02 tba  

Schedule (tutorials)

DateTopicDiscussed
24.10
31.10Vertex Coloringprevious lecture, upcoming exercises
07.11Synchronizationprevious lecture, exercise sheet 01
14.11Impossibility of Consensusprevious lecture, exercise sheet 02
21.11Reaching Consensusprevious lecture, exercise sheet 03, upcoming exercises
28.11Maximal Independent Setprevious lecture, exercise sheet 04, upcoming exercises
05.12Minimum Spanning Treesprevious lecture, exercise sheet 05
12.12Hardness of MST Construction 
19.12
26.12(Christmas Break)
02.01(Christmas Break)
09.01  
16.01  
23.01  
30.01  
06.02  

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