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 |
---|---|
Lecturers | Christoph 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 |
|
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) | Recording | Slides |
2021-04-19 | Models, context to the HtCYC lecture | (none) | Recording | Slides |
2021-04-21 | Limits on Tolerance - I | Chapter 9 | Recording | Slides |
2021-04-26 | Limits on Tolerance - II | Recording | Slides | |
2021-04-28 | Limits on Tolerance - III | Recording | ||
2021-05-03 | Limits on Tolerance - IV | Recording | Slides | |
2021-05-05 | Synchronizing by Approximate Agreement - I | Chapter 10 | Recording | Slides |
2021-05-10 | Synchronizing by Approximate Agreement - II | Recording | Slides | |
2021-05-12 | Low-Degree Clock Distribution Networks - I | Chapter 11 | Recording | Slides |
2021-05-17 | Low-Degree Clock Distribution Networks - II | Recording | Slides | |
2021-05-19 | Low-Degree Clock Distribution Networks - III | Recording | Slides | |
2021-05-24 | None (Whitmonday) | |||
2021-05-26 | Self-stabilization and Recovery - I | Chapter 12 | Recording | Slides |
2021-05-31 | Self-stabilization and Recovery - II | Recording | Slides | |
2021-06-02 | Self-stabilization and Recovery - III | Recording | Slides | |
2021-06-07 | Self-stabilizing Lynch-Welch Algorithm - I | Chapter 13 | Recording | Slides |
2021-06-09 | Self-stabilizing Lynch-Welch Algorithm - II | Recording | Slides | |
2021-06-14 | Consensus - I | Chapter 14 | Recording | Slides |
2021-06-16 | Consensus - II | Recording | Slides | |
2021-06-21 | Consensus - III | Recording | Slides | |
2021-06-23 | Self-stabilizing Pulse Synchronization - I | Chapter 15 | Recording | (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 - I | Chapter 16 | Recording | (chapter PDF) |
2021-07-07 | Synchronous Counting - II | Recording | ||
2021-07-12 | Fault-tolerant Clock Distribution - I | Chapter 17 | Recording | (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
- Instructions for your assignments (updated date on 2021-04-12, update 'bonus questions' on 2021-04-15)
- Context, motivation, model, and (a) task of the lecture (fixed formatting 2021-04-15)
- Reading material for the chapters: See above table
(Ch. 11 reuploaded on 2021-05-10; Ch. 11 sessions preponed from 2021-05-17 to 2021-05-12 on 2021-05-11; Ch. 12 extended and reuploaded on 2021-05-21; Ch. 12 extended again and reuploaded on 2021-05-21; Ch 13 fixed a typo on 2021-06-11; Ch. 15 completed on 2021-06-20.) - Supplementary material Ch. 11: moore.vhdl, gate_level_register_grid.v (plus some private files, ask if you haven't received them yet.)
- Appendix: Basic math definitions and theorems (fixed formatting 2021-04-15)
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.