Keeping Time in Distributed Systems
Advanced Course, 2+2
Basic Information
| Lectures: | Friday, 10:15 - 12:00, E1.4 024 |
|---|---|
| Lecturer: | Christoph Lenzen |
| First lecture: | 26.04.2019 |
| Tutorials: | Tuesday, 12:15-14:00, E1.4 023 |
| Assistant: | Will Rosenbaum |
| First tutorial: | 30.04.2019 |
| Credits: | 6 |
| Exam: | There will be oral exams at the end of the semenster. |
| 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. |
| Mailing List: | Please subscribe to our mailing list to enroll in the course. |
Description
In this course, we discuss how to maintain accurate synchronization in distributed systems. Essentially, this encompasses any system in which keeping a well-synchronized common notion of time is crucial, as clock synchronization is an inherently distributed task. For instance, the presented techniques are suitable for clocking computer chips or larger networks on chips, but may equally well be employed on a larger scale, like data centers or a global network. The focus of the lecture lies on a conceptual understanding of algorithmic techniques and proving worst-case guarantees mathematically. Particular emphasis is given to strong, possibly surprising, fault-tolerance properties and how they can be achieved.
No prerequisites beyond basic familiarity with mathematical reasoning are assumed or required for this course. This course is a good starting point for getting involved with the current research topics of the group.
Evaluation
Grades for he course will computed as follows:
- Homework (25%). There is a homework assignment corresponding to every lecture (except for the final lecture). Assignments are due on Friday by 17:00 one week after the corresponding lecture was given. Assignments may be handed in during lecture, emailed, or given directly to Will or Christoph. Students may work in small groups (up to 4 people), and each group may submit a single assignment. You are encouraged to discuss homework problems, but the written work you submit must be your own.
- Participation (25%). Attendence at the weekly discussion session is mandatory. During the discussion sessions, students will present a brief (10-15 minute) recap of the previous lecture, and solutions to previous homework problems. Please volunteer in advance if you want to present a particular lecture/homework problem.
- Oral Final Exam (50%). Final evaluation will be based on an oral final exam. Details to be announced.
Schedule
| Date and Video | Lecture Note | Exercise Sheet | Exercise Due | Discussed On |
|---|---|---|---|---|
| 26.04.2019 | Global Sync | Sheet 1 (solution) | 03.05.2019 | 07.05.2019 |
| 03.05.2019 | Gradient Lower | Sheet 2 (solution) | 10.05.2019 | 14.05.2019 |
| 10.05.2019 | Gradient (Appendix) | Sheet 3 (solution) | 17.05.2019 | 21.05.2019 |
| 17.05.2019 | Fault Tolerant | Sheet 4 (solution) | 24.05.2019 | 28.05.2019 |
| 24.05.2019 | Approx Agreement | Sheet 5 (solution) | 31.05.2019 | 04.06.2019 |
| 31.05.2019 | Metastability | Sheet 6 (solution) | 07.06.2019 | 11.06.2019 |
| 07.06.2019 | Meta Lynch Welch | Sheet 7 (solution) | 14.06.2019 | 18.06.2019 |
| 14.06.2019 | MC Sorting | Sheet 8 (solution) | 21.06.2019 | 25.06.2019 |
| 21.06.2019 | Self Stabilization I | Sheet 9 (solution) | 28.06.2019 | 02.07.2019 |
| 28.06.2019 | Consensus | Sheet 10 (solution) | 05.07.2019 | 09.07.2019 |
| 05.07.2019 | Synchronous Counting | Sheet 11 (solution) | ||
| 12.07.2019 | Pulse Sync | Sheet 12 | ||
| 19.07.2019 | Clock Distribution |
Announcements
- On the week of 30 April, the lecture and discussion session will be swapped. That is, Lecture 2 will occur on Tuesday, 30 April, 12:15–14:00 in room 024, and the discussion session will be on Friday, 3 May, 10:15–12:00 also in room 024. Note that homework assignment 2 will be due on Friday, 10 April.
Material
Cumulative script, including notational definitions (standalone "Notations" chapter).