Clock Synchronization and Adversarial Fault Tolerance

Advanced Course, 4

Basic Information

Lectures:Online Zoom Link: https://cs-uni-saarland-de.zoom.us/j/95062856565
For password: check the mailing list https://lists.mpi-inf.mpg.de/listinfo/csaft-2021
LecturersChristoph Lenzen and Danny Dolev
Teaching Assistant:Ben Wiederhake
First lecture:2021-04-14 (Wednesday, 12-14)
Tutorials:There will be no tutorials for this course
Session Slots:Monday 12:15-14:00
Wednesday 12:15-14:00
Assistant:Shreyas Srinivas, Johannes Bund
Credits:6
Exam:Written submission
Registration
  • To participate in this course, it is essential to register on the course mailing list: https://lists.mpi-inf.mpg.de/listinfo/csaft-2021
  • In order to take the exam and get grades, please register for the course on HISPOS (or the equivalent systems for your programme) before 2021-07-19.
Prerequisites:No prerequisites beyond basic familiarity with mathematical reasoning are required. It is helpful but not essential to understand basic elements of digital circuits. Note in particular that last semester's course "How to clock your computer" is NOT a prerequisite.
Mailing List:https://lists.mpi-inf.mpg.de/listinfo/csaft-2021

Announcements

  • Please check out the instructions for assignments file in the Materials section.
  • Please note that the deadline for HISPOS registration for SIC students is FIXME
  • Having considered multiple options, we have chosen to use Zoom as the platform for this course. Please read the notes about Zoom and data privacy at the bottom of this page.
  • Register for the course via the mailing list: https://lists.mpi-inf.mpg.de/listinfo/csaft-2021 . Registration to the mailing list helps us know who is taking the course, communicate important announcements, discuss the course contents, etc. It does not automatically imply registration for the exams and grades. For this, please check the registration requirements of your respective programmes.
  • External students are welcome to attend the course. If you are not enrolled with Saarland University, but would like to take credit for the course at your university, please contact us early on. We will then see whether an arrangement with your university can be found.

Description

What this course is about:

Computers chips are devices that are required to implement the abstraction of Boolean logic. Ideally, this abstraction is maintained when the outputs of the circuits on a chip instantaneously and reliably reflect the input signals, and all parts of the chip are perfectly synchronized by a clock signal to maintain temporal sanity. This course takes a close look at how this synchronization can be achieved in spite of transient and permanent faults. We will also explore some fundamental limitations resulting from (the possibility of) such faults.

In particular, we deal with issues related to fault tolerance, i.e., when one or more clock domains behave in unexpected or even malicious ways. The course studies these issues from a theoretical angle through the lense of mathematical proofs. At the same time, the devised algorithms are simple and practical enough to be implemented on physical chips, and the theory is informed by real-world constraints arising from hardware and the unforgiving need for efficiency.

Prior knowledge on digital logic, analog chip design, or results on fault-tolerance from distributed computing can provide useful context to attendants, but no prerequisites beyond basic familiarity with mathematical reasoning are assumed or required for this course. In particular, we do not assume any familiarity with our previous course. Both courses are a good starting points for getting involved with the current research topics of our group.

Course Format

This course does not follow a traditional classroom model. You are expected to study reading assignments before the live online sessions, in which the lecturers will provide additional context for the topics. Reading this material and providing short summaries is the lion's share of the course work outside of the sessions. Beside presentations by the lecturers, the sessions will contain Q&A sessions at the beginning of each chapter, and live exercises in breakout rooms. Active participation is highly encouraged and contributes to grades.

To be successful in this course, you will need to read the recommended material, understand it, analyze it, question it, and then reconstruct it in your own way. You will have to hand in a short summary of the material for each major topic, where, in addition to the contents, you will describe your thoughts and questions on it. These submissions contribute a total of 25% for your final grade. Another 25% will be determined from your active participation in the sessions.

At the end of the semester, you will receive an assignment comprising of a number of questions on one of the major topics of your choice. You will then have two weeks to solve these questions and explain your solutions in writing. This involves extracting and presenting the relevant context from the reading material, in a way that clearly conveys the key ideas underlying your solutions. This final assignment will contribute the remaining 50% of your grade.

Evaluation

Grades for he course will computed as follows:

  • Topic Summaries (25%). There will be 9 topics. Hence, 9 summaries will be expected throughout the semester. Summaries are individual pieces of work. We encourage you to discuss the material with your fellow classmates, but the final work must be your own and reflect your understanding and insights into the topic.
  • Participation (25%). Attending the sessions is highly recommended, since the class discussions will be graded.
  • Final Submission (50%). Final evaluation will be based on a written submission that solves some tailored questions and summarizes the relevant material for these solutions, for a topic of your choice.

For the topic summaries and the participation, the two worst individual grades will be discarded (in total, not individually for each category). (Further) absences can be justified, but require a medical certificate or equivalent proof.

Schedule

Date Topic Reading Material Recording Slides
2021-04-14 Introduction, overview (none) RecordingSlides
2021-04-19 Models, context to the HtCYC lecture (none) RecordingSlides
2021-04-21 Limits on Tolerance - IChapter 9RecordingSlides
2021-04-26 Limits on Tolerance - II   RecordingSlides
2021-04-28 Limits on Tolerance - III   Recording  
2021-05-03 Limits on Tolerance - IV   RecordingSlides
2021-05-05 Synchronizing by Approximate Agreement - IChapter 10RecordingSlides
2021-05-10 Synchronizing by Approximate Agreement - II   RecordingSlides
2021-05-12 Low-Degree Clock Distribution Networks - IChapter 11RecordingSlides
2021-05-17 Low-Degree Clock Distribution Networks - II   RecordingSlides
2021-05-19 Low-Degree Clock Distribution Networks - III   RecordingSlides
2021-05-24 None (Whitmonday)      
2021-05-26 Self-stabilization and Recovery - IChapter 12RecordingSlides
2021-05-31 Self-stabilization and Recovery - II   RecordingSlides
2021-06-02 Self-stabilization and Recovery - III   RecordingSlides
2021-06-07 Self-stabilizing Lynch-Welch Algorithm - IChapter 13RecordingSlides
2021-06-09 Self-stabilizing Lynch-Welch Algorithm - II   RecordingSlides
2021-06-14 Consensus - IChapter 14RecordingSlides
2021-06-16 Consensus - II   RecordingSlides
2021-06-21 Consensus - III   RecordingSlides
2021-06-23 Self-stabilizing Pulse Synchronization - IChapter 15Recording (chapter PDF)
2021-06-28 Self-stabilizing Pulse Synchronization - II   Recording  
2021-06-30 Self-stabilizing Pulse Synchronization - III   Recording  
2021-07-05 Synchronous Counting - IChapter 16Recording (chapter PDF)
2021-07-07 Synchronous Counting - II   Recording  
2021-07-12 Fault-tolerant Clock Distribution - IChapter 17Recording (chapter PDF)
2021-07-14 Fault-tolerant Clock Distribution - II   Recording  
2021-07-19 None      
2021-07-21 Summary / Wrap-up n/a Recording  

Material

Platform and Privacy

We have decided to use Zoom as a videoconferencing service. Note that this provider (Zoom Video
Communications, Inc., 55 Almaden Blvd, Suite 600, San Jose, CA 95113, USA) can access all data that
you provide when registering for the video conference. If you do not provide personal data during
the registration, there is still a possibility that Zoom identifies you using your IP address. We
would not have decided to use Zoom if we considered this as a significant risk. As an additional
precaution, we have opted to use European computing centers. Should you still have privacy concerns
(and are not using an Internet Service Provider that cannot map IP addresses to your name), we
suggest using an anonymization service such as Tor (https://www.torproject.org/)

You can find Zoom's complete privacy policy at: zoom.us/de-de/privacy.html

We would be happy if we could create a pleasant lecture environment despite the current situation.
Personal interactions, with your microphone and camera switched on, may contribute to this
environment. We also encourage you to ask questions verbally. Note that this is voluntary. You may
switch off both your camera and your microphone, and register under a pseudonym. Questions are
still possible, in particular using the chat function.