News
06.02.2023
|
Schedule for Q&A session and examDear Students, as discussed in the last lecture today, we will have a Q&A session on Monday, 20.02.2023, 10 a.m. Also, as agreed upon earlier, the one-week take-home exam will cover chapter 5,6 & 7. It will be handed out on Friday, 24.02.2023; the... Read more Dear Students, as discussed in the last lecture today, we will have a Q&A session on Monday, 20.02.2023, 10 a.m. Also, as agreed upon earlier, the one-week take-home exam will cover chapter 5,6 & 7. It will be handed out on Friday, 24.02.2023; the respective submission is due by Friday, 03.03.2023. Further details will be clarified in and after the Q&A. Best, Sophie |
01.02.2023
|
Reminder: Exam RegistrationDear Students, please remember to register yourself in the LSF/HISPOS by Wednesday, 08.02.2023, 23:59 if you would like to take the exam. Best, Sophie |
25.01.2023
|
Ninth AssignmentDear Students, the last book chapter covered this semester is online now. Please submit your summary by Wednesday, 01.02.2023, 10:00 a.m. Best, Sophie |
18.01.2023
|
Eight AssignmentDear Students, the book chapter on Synchronous Counting is online now. Please submit your summary by next Wednesday, 25.01.2023, 10:00 a.m. Best, Sophie |
07.01.2023
|
No lecture on MondayDear Students, Unfortunately we have to cancel this Monday's (09.01) lecture. Best, Sophie |
04.01.2023
|
Seventh ChapterDear Students, the book chapter on Self-Stabilising Pulse Synchronisation is online now. The corresponding summary is due on Wednesday, 11.01.2023 10:00 a.m. Best, Sophie |
22.12.2022
|
Sixth AssignmentDear students, the seventh chapter is online now. The corresponding summary is due by Monday, 02.01.2023 10:00 a.m.
Merry Christmas & a happy New Year!
Best, Sophie |
07.12.2022
|
Fifth AssignmentDear Students, the rather short sixth chapter on a self-stabilising version of the Lynch-Welch algorithm is online now. The corresponding summary is due on Wednesday, 14.12.2022, 10:00 a.m. Best, Sophie |
29.11.2022
|
Fourth AssignmentDear students, the fifth book chapter is available in the materials section. Please submit your summary by Monday, 05.12, 10:00 a.m. Best, Sophie |
16.11.2022
|
Third AssignmentDear Students, the chapter on low-degree clock distribution networks is now available in the materials section. Please submit your summary by Wednesday, 23.11, 10:00 a.m. Best, Sophie |
14.11.2022
|
Sample SummaryDear Students, I uploaded a sample summary of chapter 9, written by a student, which meets what we expect of an excellent submission. Best, Sophie |
08.11.2022
|
Second AssignmentDear Students, the third book chapter "Synchronising by Approximate Agreement" is available in the materials section. Please submit your summary on your personal CMS status page by Wednesday, 16.11, 10:00 a.m. Best, Sophie |
30.10.2022
|
ClarificationsDear Students, the definitions missing in Chapter 9 are now available in a separate document in the materials section. Many thanks to the person who pointed out this incompleteness! Apologies and best regards, Sophie |
26.10.2022
|
Model ChapterDear Students, please take note that I accidentally published the wrong chapter 1 (Models) so please make sure to read the correct updated one! Best, Sophie |
26.10.2022
|
Reading Material & First SummaryDear Students, the introductory chapter on models is now available in the materials section. You don't need to write a summary of this specific chapter but please read it before the lecture Monday morning.
The first mandatory assignment consists in... Read more Dear Students, the introductory chapter on models is now available in the materials section. You don't need to write a summary of this specific chapter but please read it before the lecture Monday morning.
The first mandatory assignment consists in writing a summary of Chapter 2 - Limits of Fault Tolerance. As mentioned earlier, I uploaded a guide on how to write a good summary in the materials section. It is due by Wednesday 02.11, 10:00 a.m.
Feel free to ask questions (by mail!) if there is something unclear!
Best, Sophie |
25.10.2022
|
First lectureDear Students, the Zoom link is available in the materials section. See you tomorrow! Sophie |
Clock Synchronization and Adversarial Fault Tolerance
People
Lecturers:
- Christoph Lenzen
- Danny Dolev
Teaching Assistant:
- Sophie Wenning
Lecture slots
Weekly lecture slots:
- Monday, 10-12
- Wednesday, 10-12
First lecture:
- Wednesday, 26.10
There are no tutorials. The lectures are online. The participation link will be sent out to registered students before the first lecture (later registrations are possible; please contact Christoph Lenzen (mail) or Sophie Wenning (mail) for receiving the link in this case).
Content overview
This course takes a close look at how clock synchronization can be achieved in spite of transient and permanent faults, i.e., what happens when one or more clock domains behave in unexpected or even malicious ways. It explores fault-tolerant clock distribution protocols, self-stabilising synchronisation algorithms as well as some fundamental limitations resulting from faults. All topics will be first studied through the lense of mathematical proofs. However, as the presented algorithms are simple and practical enough to be implemented on physical chips, we also will investigate real-world constraints arising from hardware and the unforgiving need for efficiency. Based on these observations, we will build bridges back to the theoretical level and try to adapt and improve our models.
Classroom model
This lecture follows the inverted classroom model. This implies that the course is structured as follows:
-
We will provide you with some reading material one week before each new lecture block and you will prepare a summary of the topic which we will grade. You are also encouraged to ask questions about aspects that you feel you have not yet properly understood. This step is intended to prepare you for the actual lecture.
-
The lecture itself aims to be interactive. The lecturers will present the topic in more detail. In a subsequent discussion we will answer your questions before moving on to jointly solved exercises designed to further deepen your understanding of the topic.
Prerequisites
No prerequisites beyond basic familiarity with mathematical reasoning are required. It can be helpful to have knowledge about (electric) circuitry and Boolean logic, but this is not mandatory. Note in particular that last semester's course "How to clock your computer" is NOT a prerequisite.
Evaluation
The grades for this course will be computed from:
- Homework assignments (25%): you have to write a short summary for each of the above chapters. These fortnightly assignments will be graded.
- Participation in class (25%): we appreciate your participation in the discussions that will form an important part of each lecture. As your contribution will be graded, attendance at the lectures is strongly recommended.
- Final written submission (50%): a final homework assignment at the end of the semester completes the assessment.