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:tba
Credits:6
Exam:tba
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)

DateTopicExerciseDue
22.10Preliminary meeting (read below)
29.10tba  
05.11tba  
12.11tba  
19.11tba  
26.11tba  
03.12tba  
10.12tba  
17.12tba  
24.12(Christmas Break)
31.12(Christmas Break)
31.12tba  
07.01tba  
14.01tba  
21.01tba  
28.01tba  
04.02tba  

Schedule (tutorials)

DateTopicDiscussed
24.10  
31.10  
07.11  
14.11  
21.11  
28.11  
05.12  
12.12  
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 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. For preparation of the preliminary meeting please read this (coming soon).
  • 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 provide a short script on notation and preliminaries for this course. (Uploaded 9.8.2019)
  • If you are interested in the material you can have a look at a previous iteration of this course
  • The complete script will be provided close to the end of the semester.