Distributed Systems (HS 2019)

Course Catalogue

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.

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.

Exercises by Rösti André, Friday 13.15-15.00 @ CAB G 57. Exercises only take place in the weeks with a lecture.

Organization by Roland Schmid.

Project Work: There will be a project during the semester, through which a quarter grade bonus can be earned. Click here for details.

Word of advice from the professor: Instead of coming to 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

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".

References

[BCS]

Blockchain Science: Distributed Ledger Technology Roger Wattenhofer Inverted Forest Publishing, 2019, ISBN 978-1793471734

Exam Preparation

The written exam takes place on Saturday, January 25th, in HIL E 1. It lasts 90 minutes and no written or electronic aids are permitted.

All material covered by lectures and exercises may be tested in the exam. We did not discuss Sections 19.4, 19.5, and 26.5, so the content of these sections is not part of the exam. We did not discuss some of the hypercubic networks (24.12-24.16), and we only discussed the f-opaque quorum system (21.4) on a high level.

Do not memorize the details of the remarks (e.g., what year UTC was established, or how the UTC format looks like; but you should know that UTC exists). Also, there is no need to learn all details of the algorithms and proofs. However, you should understand their concepts and ideas, so that you could explain them, or discuss variants.

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. 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.

A Q&A session will be held on Friday, January 17th, at 1pm in ETF E 1. We will not answer questions after the Q&A session anymore.

Important: You need to submit your questions no later than 72 hours prior to the session to give the responsible assistants enough time to find satisfying answers to your questions. That is, the deadline for submitting questions is Tuesday, January 14th, 13:00. Please submit your questions here. If you only bring up your questions in the Q&A session, we cannot guarantee having answers for you.

Please keep in mind that this Q&A session will cover only the Distributed Systems part of the lecture.

The questions and answers from the Q&A session are available here.

This Year's Exam

For your nostalgic and enlightening pleasure, we have made this year's exam available here. Please note, that the sample solution merely contains a single correct solution for each task which would have netted full points, but other solutions may also have received partial or full points.

© 2024 DISCO, TIK, ETH Zurich | Imprint | Last updated: Mon, 31 Aug 2020 21:07.