|Q&A Sessions:||Tuesday, 12:00 - 14:00, virtual (first session: 03.11.2020)|
|Exercise Sessions:||Thursday, 16:00 - 18:00, virtual (first session: 05.11.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.|
|Registration:||(1) subscribe to our mailing list (ToDS2021)|
(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
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.
|Q&A||Exercise||Topic||Script (Last Update)||Exercise Sheet (Last Update)|
|Notation and Preliminaries||ToDS_notation (26.08.2020)|
|17.11.||19.11.||Impossibility of Consensus|
|01.12.||03.12.||Maximal Independent Set|
|08.12.||10.12.||Minimum Spanning Trees|
|15.12.||17.12.||Hardness of MST Construction|
|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|
|02.02.||04.02.||The Port Numbering Model|
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:
- 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 the (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 person or via the mailing list, where we can chime in)
- Q&A session: ask your questions and actively participate in the discussions
- 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 ok if this affects your hand-in; simply state where the ideas are from)
- 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.