Theory of Distributed Systems

Advanced Course, 2+2

Basic Information

Lectures:Thursday, 10:15 - 12:00, E1.4 024
Lecturer:Christoph Lenzen
First lecture:26.10.2017
Tutorials:Monday, 10:15 - 12:00, E1.4 024
Assistant:Ben Wiederhake
First tutorial:30.10.2017
Credits:6
Exam:08.02.2018
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

DateTopicExercise SheetExercise DueDiscussed On
26.10.2017ColoringSheet 102.11.2017, 10:1506.11.2017
02.11.2017SynchronizersSheet 209.11.2017, 10:1513.11.2017
09.11.2017Impossibility of ConsensusSheet 316.11.2017, 10:1520.11.2017
16.11.2017ConsensusSheet 423.11.2017, 10:1527.11.2017
23.11.2017Maximal Independent SetSheet 530.11.2017, 10:1504.12.2017
30.11.2017Minimum Spanning TreeSheet 607.12.2017, 10:1511.12.2017
07.12.2017Hardness of MSTSheet 714.12.2017, 10:1518.12.2017
14.12.2017RoutingSheet 821.12.2017, 10:1508.01.2018
21.12.2017Guest Lecture by Emanuele Natalen/an/an/a
28.12.2017— (Christmas Break)n/an/an/a
04.01.2018Self-StabilizationSheet 911.01.2018, 10:1515.01.2018
11.01.2018MutEx + S&CSheet 1018.01.2018, 10:1522.01.2018
18.01.2018Shared CountersSheet 1125.01.2018, 10:1529.01.2018
25.01.2018Port NumberingSheet 1201.02.2018, 10:1505.02.2018
08.02.2018Examn/an/an/a

Announcements

  • Read and believe how we would like to run this course.
  • Subscription to our mailing list  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

  • Some notation and preliminaries required for this course.
  • The complete script Available towards the end of the semester.
  • Lecture notes MIS guest lecture Available after it happened.