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 VideoLecture NoteExercise SheetExercise DueDiscussed On
26.04.2019Global SyncSheet 1 (solution)03.05.201907.05.2019
03.05.2019Gradient LowerSheet 2 (solution)10.05.201914.05.2019
10.05.2019Gradient (Appendix)Sheet 3 (solution)17.05.201921.05.2019
17.05.2019Fault TolerantSheet 424.05.201928.05.2019
24.05.2019Approx Agreement   
31.05.2019Metastability   
07.06.2019Meta Lynch Welch   
14.06.2019MC Sorting   
21.06.2019Self Stabilization I   
28.06.2019Consensus   
05.07.2019Synchronous Counting   
12.07.2019Pulse Sync   
19.07.2019Clock 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).