Theory of Distributed Systems

Advanced Course, 2+2

Basic Information

Q&A Sessions:Tuesday, 12:00 - 14:00, virtual (first session: 03.11.2020)
Lecturer:Christoph Lenzen
Exercise Sessions:Thursday, 16:00 - 18:00, virtual (first session: 05.11.2020)
Assistant:Corinna Coupette
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.
Credits:6
Registration:(1) subscribe to our mailing list (ToDS2021) (you will get the login credentials for all sessions after subscription)
(2) register for the course via the LSF (or whatever the equivalent for your course of studies)
Grading:25% participation in lectures and tutorials
25% homework assignments
50% oral exam at the end of the semester
Exam:TBD (February)

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

Q&AExerciseTopicScript (Last Update)Exercise Sheet (Last Update)
  Notation and PreliminariesToDS_notation (26.08.2020) 
03.11.05.11.Vertex ColoringToDS_01 (29.10.2020)Exercise_01 (03.11.2020)
10.11.12.11.SynchronizersToDS_02 (05.11.2020)Exercise_02 (05.11.2020)
17.11.19.11.Impossibility of ConsensusToDS_03 (12.11.2020)Exercise_03 (12.11.2020)
24.11.26.11.Reaching ConsensusToDS_04 (19.11.2020)Exercise_04 (19.11.2020)
01.12.03.12.Maximal Independent SetToDS_05 (26.11.2020)Exercise_05 (26.11.2020)
08.12.10.12.Minimum Spanning Trees  
15.12.17.12.Hardness of MST Construction  
22.12.24.12.(Christmas Break)
29.12.31.12.(Christmas Break)
05.01.07.01.Distance Approximation and Routing  
12.01.14.01.Self-Stabilization and Recovery  
19.01.21.01.Mutual Exclusion and Store & Collect  
26.01.28.01.Shared Counters  
02.02.04.02.The Port Numbering Model  

Workflow

This course is run as a flipped class room. There is not going to be a lecture. Instead, every week there are going to be a Q&A session and an exercise session.
Your task is to prepare each of these sessions. For the Q&A session, this means that you bring your questions, ideas, and requests about discussing parts of the material interactively. For the exercise session, this means that you have composed some preliminary thoughts and ideas on how to tackle the exercises, which then are discussed and executed in the exercise session.

A typical week looks as follows:

  1. Q&A session preparation (expected 3-5 hours of work):
    • read the script (and optionally view last year's video) for the upcoming lecture
    • hand in a one-page summary of the content of the upcoming lecture, abstracting the main ideas in your own words, until the night before the lecture 
    • write down (at least) three of the most important obstacles to understanding you face(d); try to clearly identify where the difficulty lies (e.g., "the proof of theorem X, specifically step Y")
    • optional, but highly encouraged: discuss the issues you and others identified (in [virtual] person or via the mailing list, where we can chime in)
  2. Q&A session: ask your questions and actively participate in the discussions
  3. exercise session preparation (expected 1 hour of work):
    • read the exercise sheet
    • hand in a write-up of your own ideas on the exercises (no full solutions expected, no more than one page per single exercise) until the night before the tutorial 
    • optional, but highly encouraged: exchange your ideas with others (it is okay if this affects your hand-in; simply state where the ideas are from)
  4. exercise session: actively contribute to the discussion developing the solutions to the exercises

As you can see, there is a much higher emphasis on the preparation of the lecture than in a standard course.
This is essential, as the Q&A session serves to complete your understanding of the lecture material.
In order for the Q&A sessions to be successful, it is imperative that you identify the issues they should focus on.

How to hand in your submissions

Please submit your summaries and exercise ideas via email to the TA (<lastname>@mpi-inf.mpg.de), adhering to the following rules:

  • Heading: "[ToDS] <{Lecture, Exercise}> <Number> Submission <Your Student ID>"; example: "[ToDS] Lecture 1 Submission 0123456"
  • Body: None that goes beyond variants of "please find attached", especially no general comments, requests, concerns etc. (use a separate email for those)
  • Attachment: one(!) PDF of reasonable size (<<10 MB) containing your submission as well as your name and your student ID(!); if you scan hand-written solutions, make sure that a reasonable person that is not you can read them
  • Attachment File Name: "ToDS_<{Lecture,Exercise}>_<Number>_Submission_<Your Student ID>.pdf"; example: "ToDS_Lecture_1_Submission_0123456.pdf"

If you do not have a Student ID (yet), use your name wherever the Student ID is required in the above.

Your submissions must arrive until midnight on the day before the session for which they are due (what matters is the timestamp of your email in the TA's inbox).