Distributed Computing
ETH Zurich

Principles of Distributed Computing (FS 2024)

Course cataloguePrevious yearPODC lecture collection

Distributed computing is essential in modern computing and communications systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as your multi-core laptop. This course introduces the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. We cover a fresh topic every week.

Bonus Task

This lecture comes with a bonus task, where you can win a grade bonus of 0.25. The bonus task is to design an interesting question about the material of this course (pretty much the same way as we later will design the exam questions). Your question should be complex enough to take about 20 minutes to solve. You submit a question (possibly containing several subquestions), along with solutions. You may take style inspiration from past exam questions (and solutions), but your question must be original. Your bonus task submission must be of high quality, submitted in the PDF format. We will not award a bonus grade for questions that merely ask about something that can easily be looked up in the script. It takes us at least 20 hours to design an exam question (initial idea, improvements, tuning, testing), so we expect that it will take you a substantial time to produce an interesting question.

There will be two deadlines, one in the middle of the semester, one towards the end. We will evaluate your exam question, and rate it as either (a) pass, (b) revision, or (c) fail. If your submission is rated (b), then you may submit a revision. You can only win the grade bonus once, so if you already scored (a) for the mid-semester deadline, submitting again for the second deadline cannot increase your grade bonus.

Deadlines: We will not use your bonus task question in the actual exam, and we will share all submissions that passed.

You should submit your question and its solution by uploading a PDF with your name, surname and email to this Polybox folder. The file should be named as name_surname.pdf. If you wish to update your submission, just submit using the form again. The submisions made after April 10th will be considered for the second deadline of May 29.

Exam

Discussion Forum

We have set up a discussion forum on the moodle course homepage. You can use this forum to ask questions about the lecture as well as the bonus assignment. As this is a discussion forum, feel free to also answer the questions of your colleagues.

Lecture Material

Chapter Title Lecture Exercises Additional Material
Chapter 0
Introduction
21.02.2023
Script [peleg] Preface, Chapter 1
Chapter 1
Vertex Coloring
21.02.2023
Script
Video
Supervised by Borna
Exercises
Solutions
[peleg] Chapter 7
Slides by S.Schmid, TU Berlin
Chapter 2
Tree Algorithms
28.03.2023
Script
Video
Supervised by Frédéric
Exercises
Solutions
[peleg] Chapter 3-5
[hkpru] Chapter 7
Slides by S.Schmid, TU Berlin
Chapter 3
Leader Election
06.03.2023
Script
Video
Supervised by Mose
Exercises
Solutions
[hkpru] Chapter 8
Slides by S.Schmid, TU Berlin
Chapter 4
Maximal Independent Set
13.03.2023
Script
Video
Supervised by Quentin
Exercises
Solutions
[peleg] Chapter 8
Slides by R. Wattenhofer
Slides by S.Schmid, TU Berlin
Chapter 5
Locality Lower Bounds
20.03.2023
Script
Video
Supervised by Diana Slides by S.Schmid, TU Berlin
Chapter 6
Global Problems
27.03.2023
Supervised by Robin Slides by R. Wattenhofer
Animation of APSP Algorithm
by Jukka Suomela
Chapter 7
Shared Objects
10.04.2023
Supervised by Quentin Slides by S.Schmid, TU Berlin
Chapter 8
Distributed Sorting
17.04.2023
Supervised by Frédéric [leighton] Chapter 1.6 & 3.5
[clr] Chapter 28
Slides by S.Schmid, TU Berlin
Chapter 9
Stabilization
24.04.2023
Supervised by Diana Slides by S.Schmid, TU Berlin
Chapter 10
To Be Determined
01.05.2023
Chapter 11
Wireless Protocols
08.05.2023
Supervised by Yann
Chapter 12
Graph Neural Networks
15.05.2023
Supervised by Andreas Graph Representation Learning
by William L. Hamilton, McGill University
Chapter 13
To Be Determined
22.05.2023
Chapter 14
Labeling Schemes
29.05.2023
Supervised by Andrei

References

These books are available at CS text book collection.

[peleg] Distributed Computing: A Locality-Sensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8
[aw] Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6
[hkpru] Dissemination of Information in Communication Networks
Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, Walter Unger.
Springer-Verlag, Berlin Heidelberg, 2005, ISBN 3-540-00846-2
[leighton] Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Frank Thomson Leighton.
Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991, ISBN 1-55860-117-1
[clr] Introduction to Algorithms
Thomas Cormen, Charles Leiserson, Ronald Rivest.
The MIT Press, 1998, ISBN 0-262-53091-0 oder 0-262-03141-8