Keeping Time in Distributed Systems

Advanced Course, 2+2

Basic Information

Lectures:

Friday, 14:15 - 16:00, E1.4 024

Lecturer:Christoph Lenzen
First lecture:13.04.2018
Tutorials:Wednesday, 14:15-16:00, E1.4 023
Assistant:Saeed Amiri
First tutorial:

17.04.2018

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.

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.

Schedule

Date and VideoLecture NoteExercise SheetExercise DueDiscussed On
13.04.2018Global SynchSheet 120.04.201824.04.2018
20.04.2018GradientSheet 227.04.201802.05.2018
27.04.2018Gradient LowerSheet 304.05.201809.05.2018
04.05.2018Fault TolerantSheet 411.05.201816.05.2018
11.05.2018Approx AgreementSheet 518.05.201823.05.2018
18.05.2018MetastabilitySheet 625.05.201830.05.2018
25.05.2018Meta Lynch WelchSheet 701.06.201806.06.2018
01.06.2018MC SortingSheet 808.06.201813.06.2018
08.06.2018Self Stabilization ISheet 915.06.201820.06.2018
15.06.2018ConsensusSheet 1022.06.201827.06.2018
22.06.2018Synchronous CountingSheet 1129.06.201804.07.2018
29.06.2018Pulse SyncSheet 1206.07.201818.07.2018
13.07.2018Clock Distribution   

Announcements

  • Sadly, the quality of the first video is too poor to read anything on the board. We will try to fix this for future videos.
  • Read and believe how we would like to run this course.
  • Subscription to our mailing list is mandatory  (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

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