Distributed Systems (HS 2021)
Note: This course is part of the course "Computer Systems" (252-0217-00L). Visit the page of the full course held together with Professor Roscoe here. The internal moodle link is here.
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 or Friday 10.15-12.00 @ CAB G 61. Also on Zoom: Meeting ID: 672 0550 6948, Password: 018029
Videos Videos of the lectures can be found on the ETH Video Portal.
Exercises Friday 14.15-16.00 @ CAB G 57. Exercises only take place in the weeks with a lecture. Also on Zoom: Meeting ID: 649 0249 7237, Password: DustyWires . Recordings of the exercise sessions can be found here.
Bonus See here for description of the bonus task, deadline for submissions, etc.
Organization by Tejaswi Nadahalli and Lukas Bürgi (lukas.buergi@asvz.ch).
Corona information: We will follow Corona guidelines from the main ETH administration. Check here for more details.
Script 2021: You can find the script for 2021 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
| 21.12.2021 | Chapter 26: Part 2. Cascade: Only the motivation (section 1) is relevant to the exam. The technical details of the paper are not exam material. |
| 15.12.2021 | Chapter 24 (Advanced Blockchains): Section 24.2 is not exam material. |
| 23.11.2021 | Chapter 19 (Consistency & Logical Time): Sections 19.3 and 19.5 are not exam material. |
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: 08-November-2021 |
--- | --- | |
|
Chapter 15 Fault Tolerance & Paxos Date: 08-November-2021 |
--- | --- | |
|
Chapter 16 Consensus Date: 12-November-2021 |
Exercises Solutions |
Exercise Slides | |
|
Chapter 17 Byzantine Agreement Date: 15-November-2021 |
--- | --- | |
|
Chapter 18 Broadcast & Shared Coins Date: 19-November-2021 |
Exercises Solutions |
Exercise Slides | |
|
Chapter 19 Consistency & Logical Time Date: 22-November-2021 |
--- | --- | |
|
Chapter 20 Time, Clocks & GPS Date: 26-November-2021 |
Exercises Solutions |
Exercise Slides | |
|
Chapter 21 Quorum Systems Date: 29-November-2021 |
--- | --- | |
|
Chapter 22 Distributed Storage Date: 03-December-2021 |
Exercises Solutions |
Exercise Slides | |
|
Chapter 23 Eventual Consistency and Bitcoin Date: 06-December-2021 |
--- | --- | |
|
Chapter 24 Advanced Blockchains Date: 10-December-2021 |
Exercises Solutions |
Exercise Slides | |
|
Chapter 25 Game Theory Date: 13-December-2021 |
--- | --- | |
|
Chapter 26 Authenticated Agreement Date: 17-December-2021 |
Exercises Solutions |
--- | |
|
Chapter 26: Part 2 Cascade Date: 17-December-2021 |
--- | --- | |
|
Chapter 27 Advanced Topics in Distributed Systems Date: 20-December-2021 |
--- | --- |
Dfinity Internet Computer DeFi Fair Ordering |
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. 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.