Distributed Systems (HS 2018)

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.

Note that the lecture takes place in roughly half of the semester weeks. The exact dates will be published on this page and subscribed students will be notified by email.

Lecture by Roger Wattenhofer, Monday or Friday 10.15-12.00 @ CAB G 61.

Exercises by Selma Steinhoff, Friday 13.15-15.00 @ CAB G 57. Exercises only take place in the weeks with a lecture.

Organization by Manuel Eichelberger.

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 non-continuous, but rather aligned with the course "Computer Systems".

A full version of the script shared with the Computer Systems course is available here. Note that not all chapters are relevant for this course. Also, this script version includes some minor changes like improved explanations and corrected typos.

Exercise Session Slides

The exercise session slides of the TAs can be found here. (Note:The slides are not official material and might contain errors!)

References

[SBC]

Distributed Ledger Technology: The Science of the Blockchain Roger Wattenhofer Inverted Forest Publishing, 2017, ISBN 978-1-54-423210-2

Exam Preparation

Generally speaking, all material covered by the lectures and the exercises may be tested in the exam.

We did not discuss Sections 13.4, 13.5, and 26.5. The content of these sections is not part of the exam.

The following are part of the exam, but we do not expect you to memorize them:

• Paxos Algo (7.3): no need to memorize 100%, but the general idea should be clear.
• Ben-Or Algos (8.15 & 11.5): no need to memorize 100%, but the general idea should be clear.
• Theorem 12.11 & 12.12: General idea, not math details.
• Section 12.5: We only did this shallowly, so you only need to know the basic idea (signatures and secret sharing make it possible to implement a shared coin).
• Advanced GPS Algos (14.31, 14.33, 14.37): no need to memorize 100%, but the general idea should be clear.
• f-opaque Quorum System (15.33-15.36): We only did this shallowly, so you only need to know the basic idea (overlap needs to be large, and as such it becomes impractical).
• Other hypercubic networks (24.12-24.16): We did not discuss these.
• All PBFT Algos (25.12, 25.15, 25.17, 25.22, 25.23, 25.24): no need to memorize 100%, but the general idea should be clear (in particular, why these parts are needed, and the intuition behind them).

Also, there is no need to memorize any remarks, just passive knowledge of all remarks is enough.

• For example, nobody will ask you how many uncles Ethereum allows, or how uncle rewards are split, or how often Ethereum produces blocks (see remarks after Definition 26.14), but we might want to know whether at all Ethereum uses a DAG-approach, or if Ethereum produces more or less blocks per hour than Bitcoin.
• Second example: We don’t want you to know in what years GMT or UTC was established, or how the UTC format looks like, or why UTC is called UTC (see remarks after Definition 14.18), but you should know that UTC exists.
• These are just two examples, all other remarks follow the same idea.

Everything else (Definitions, Algorithms, Proofs) is part of the exam.

For practice and to get a feel for the style of questions in the exam you may consult exams from previous years provided here: HS09, HS10, HS11, HS12, HS13, HS15, HS16. Beware that the topics covered have shifted around a little over the years. For instance, this year's new chapters are "Broadcast & Shared Coins", "Time, Clocks & GPS" and "Advanced Blockchain Topics". Also, this year's exam will be in English!

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

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