Keeping Time in Distributed Systems

Advanced Course, 2+2

Basic Information


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:



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.


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.


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.


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 4 (solution)24.05.201928.05.2019
24.05.2019Approx AgreementSheet 5 (solution)31.05.201904.06.2019
31.05.2019MetastabilitySheet 6 (solution)07.06.201911.06.2019
07.06.2019Meta Lynch WelchSheet 7 (solution)14.06.201918.06.2019
14.06.2019MC SortingSheet 8 (solution)21.06.201925.06.2019
21.06.2019Self Stabilization ISheet 9 (solution)28.06.201902.07.2019
28.06.2019ConsensusSheet 10 (solution)05.07.201909.07.2019
05.07.2019Synchronous CountingSheet 11 (solution)  
12.07.2019Pulse SyncSheet 12  
19.07.2019Clock Distribution   



  • 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.


Cumulative script, including notational definitions (standalone "Notations" chapter).