Distributed Systems (HS 2023)
Note: This course is part of the course "Computer Systems" (252-0217-00L), but can also be taken as a standalone course: "Distributed Systems" 227-0555-00L. For the full course held together with Professor Roscoe visit the corresponding webpage and the corresponding internal moodle.
This course introduces the fundamentals of distributed systems. We study different protocols and algorithms that allow for fault-tolerant operation, and discuss practical systems that implement these techniques. The objective of the course is for students to understand the theoretical principles and practical considerations of distributed systems. This includes the main models of fault-tolerant distributed systems (crash failures, byzantine failures, and selfishness), and the most important algorithms, protocols and impossibility results. By the end of the course, students should be able to reason about various concepts such as consistency, durability, availability, fault tolerance, and replication.
Topics: client-server, serialization, two-phase protocols, three-phase protocols, paxos, two generals problem, crash failures, impossibility of consensus, byzantine failures, agreement, termination, validity, byzantine agreement, king algorithm, asynchronous byzantine agreement, authentication, signatures, reliable and atomic broadcast, eventual consistency, blockchain, cryptocurrencies such as bitcoin and ethereum, proof-of-work, proof-of-*, smart contracts, quorum systems, fault-tolerant protocols such as piChain or pbft, distributed storage, distributed hash tables, physical and logical clocks, causality, selfishness, game theoretic models, mechanism design.
Course pre-requisites: None.
Course language: English.
Lecture by Roger Wattenhofer, Monday and Friday 10.15-12.00 @ CAB G 61.
Videos Videos of the lectures can be found on the ETH Video Portal.
Exercises Wednesday 10.15-12.00 @ HG E 21 lead by Loic Holbein (holbeinl@student.ethz.ch). Exercises start one week after lecture start. We will not provide recordings of the exercise sessions.
Q&A Students can self-enroll using the password received by email in order to access the moodle Q&A board (shared with Computer Systems).
Organization by Yann Vonlanthen.
Last year's script: You can find last year’s script here.
Word of advice from the professor: Instead of attending this course, you can also just read The Saddest Moment by James Mickens, the guy who continuously tried to convince me that having vodka shots at a local Denny's at 3am is how I should spend my nights. Just reading Mickens will not give you any credits though.
News
| 03.09.2023 | Course website updated. |
| 31.10.2023 | The course starts on November 6. The first exercise session will take place on November 15. |
| 15.11.2023 | Option to access a Q&A forum was added (see above). |
| 16.11.2023 | Prof. Wattenhofer has been involved in an accident, during his recovery Teaching Assistants will assume teaching duties. |
| 17.11.2023 | Chapter 18 and chapter 19 will be taught by Andrei Constantinescu. |
| 20.11.2023 | Chapter 19 notes were updated (small fixes and new remark). |
| 23.11.2023 | Chapter 18 (Broadcast & Shared Coins): Section 18.4 is not exam material. |
| 24.11.2023 | Chapter 20 and chapter 21 will be taught by Diana Ghinea. |
| 24.11.2023 | Chapter 20 notes were updated (small fixes). |
| 30.11.2023 | Chapter 22 will be taught by Robin Fritsch and Till Aczel. |
| 03.12.2023 | Chapter 23 and chapter 25 will be taught by Yann Vonlanthen. |
| 04.12.2023 | There will be no lecture on Friday, 08.12.23. Instead, the lecture is flipped, meaning you can watch the set of videos at your own pace. |
| 06.12.2023 | Chapter 16 exercise slides, assignment and solution were updated to match the Ben-Or pseudocode from the lecture notes. |
| 19.12.2023 | Definition 24.16 was updated in the script. |
| 05.01.2023 | Added an optional bonus video for chapter 24. |
Lecture Material
Lecture material and exercise sheets will be uploaded here as the lecture progresses. Note that chapter numbers are aligned with the course "Computer Systems".
| Title | Lecture Notes | Exercises | Additional Material |
|---|---|---|---|
|
Chapter 14 Introduction Date: 06-November-2023 |
--- | --- | |
|
Chapter 15 Fault Tolerance & Paxos Date: 06-November-2023 |
--- | Recording from 2020 | |
|
Chapter 16 Consensus Date: 10-November-2023 |
Exercises Solutions |
Recording from 2020 Exercise Slides |
|
|
Chapter 17 Byzantine Agreement Date: 14-November-2023 |
--- | Recording from 2020 | |
|
Chapter 18 Broadcast & Shared Coins Date: 17-November-2023 |
Exercises Solutions |
Recording from 2020 Exercise Slides |
|
|
Chapter 19 Quorum Systems Date: 21-November-2023 |
--- | Recording from 2020 | |
|
Chapter 20 Approximate Agreement Date: 24-November-2023 |
Exercises Solutions |
New Recording Exercise Slides |
|
|
Chapter 21 Consistency & Logical Time Date: 27-November-2023 |
--- | Recording from 2020 | |
|
Chapter 22 Time, Clocks & GPS Date: 01-December-2023 |
Exercises Solutions |
Recording from 2020 Exercise Slides |
|
|
Chapter 23 Distributed Storage Date: 04-December-2023 |
--- | Recording from 2020 | |
|
Chapter 24 Game Theory Date: 08-December-2023 |
PDF Flipped Classrom Playlist |
Exercises Solutions |
Recording from 2020 Exercise Slides Bonus Video |
|
Chapter 25 Eventual Consistency and Bitcoin Date: 11-December-2023 |
--- | Recording from 2020 | |
|
Chapter 26 Internet Computer Date: 15-December-2023 |
--- |
Recording Internet Computer Slides |
|
|
Chapter 27 Advanced Blockchains Date: 18-December-2023 |
Exercises Solutions |
Recording Lecture Slides Exercise Slides |
|
|
No lecture Date: 22-December-2023 |
--- | --- | --- |
Exam Preparation
To get an idea for the style of questions in the exam, you may consult exams from previous years: HS09, HS10, HS11, HS12, HS13, HS14, HS15, HS16, HS18, HS19, HS20, HS21. HS22. Beware that the topics covered have shifted around a little over the years, so some older exams have questions about topics that are not in the lecture anymore. Some of the older exams are in German, but this year’s exam is in English.