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. In the same way as we later will design the exam questions, your task is to devise an interesting problem about the material of this course (possibly containing several subquestions) along with high-quality solutions. Your problem should be complex enough to take about 20 minutes to solve, and no bonus grade will be awarded for questions that merely ask about something that can easily be looked up in the script (definition, algorithm, etc). You may take style inspiration from past exam questions (and solutions), but your question must be original. 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 submission and rate it as either (a) pass, (b) revision, or (c) fail, based on the originality of the problem, the correctness and the novelty of the solution (i.e. does not directly follow from an algorithm seen in the lecture), and to a certain extent, on the overall readability of your submission (both the questions and the solutions should be cristal-clear and leave no room to interpretation). If your submission is rated (b), you will have two weeks to submit a revision. In case of a (c), major revisions or a whole new idea may be needed and you will only be able to re-submit at the second deadline. If you scored (a) at the mid-semester deadline, congratulations: you already won the bonus grade and submitting again at the second deadline will not improve your grade.

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.

Approved Bonus Tasks For Exam Practice

In the following Polybox folder you can find the bonus tasks that were accepted.

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
Exercises
Solutions
Chapter 6
Global Problems
27.03.2023
Script
Video
Supervised by Robin
Exercises
Solutions
Slides by R. Wattenhofer
Animation of APSP Algorithm
by Jukka Suomela
Chapter 7
Shared Objects
10.04.2023
Script
Video
Supervised by Quentin
Exercises
Solutions
Slides by S.Schmid, TU Berlin
Chapter 8
Distributed Sorting
17.04.2023
Script
Video
Supervised by Frédéric
Exercises
Solutions
[leighton] Chapter 1.6 & 3.5
[clr] Chapter 28
Slides by S.Schmid, TU Berlin
Chapter 9
Stabilization
24.04.2023
Script
Video
Supervised by Diana
Exercises
Solutions
No lecture (public holyday)
01.05.2023
Chapter 10
Wireless Protocols
08.05.2023
Taught by Damien Berriaud
Script
Video
Supervised by Yann
Exercises
Solutions
Chapter 11
Graph Neural Networks
15.05.2023
Script
Video
Supervised by Andreas
Exercises
Solutions
Graph Representation Learning
by William L. Hamilton, McGill University
Chapter 12
Matching
22.05.2023
Taught by Dr. Manuela Fischer
Script
Video
Supervised by Damien
Exercises
Solutions
Original Paper
Slides by M.Fischer, ETH Zürich
Chapter 13
Labeling Schemes
29.05.2023
Script
Video
Supervised by Andrei
Exercises
Solutions

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