Principles of Distributed Computing (FS 2025)

Course catalogue • Previous year • PODC 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.

• Course pre-requisites: Interest in algorithmic problems. (No particular course needed.)
• Course language: English
• Lecture by Manuela Fischer (Roger Wattenhofer is on sabbatical), Wednesdays 8-10: CAB G 61.
• Lectures are in-person only. Recordings from previous years will however be available, and photographs of the blackboards can be found here.
• Exercises organized by Damien Berriaud and Marc Dufay.
  • Exercise A: Wednesdays 14-16: ETZ E 6,
  • Exercise B: Wednesdays 16-18: ETZ E 6.
  • Both exercise sessions offer identical content. Please visit the exercise session which better fits your personal schedule.
  • The exercise session for a given topic happens one week after the corresponding lecture.
  • As a consequence, there will be no exercise session during the first week (19.02.25)

Bonus Task

Each week, students will be able to submit an original problem based on a topic from a previous lecture. Students coming up with an interesting problem about the material of this course (possibly containing several subquestions) along with an high-quality solution will be awarded a grade bonus of 0.25 and their problem will be shared with other students.

Your problem should be complex enough to take about 20 minutes to solve, and should not 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.

The deadline to submit a problem for a given topic is two weeks after the corresponding lecture. For example, the deadline to submit a problem related to Vertex Coloring will be on the 5th of March. The problem has to be sent by mail to the TA who organized the exercise session for the topic. A student may submit multiple problems but will be awarded the grade bonus at most once.

Exam

• The exam will take place in August.
• You are allowed to bring any written material you like (lecture notes, books, personal notes,...), but no electronic devices whatsoever (no calculator, phone, laptop, headphones,...).
• The exam will last 2 hours and consist of 120 points.
• Here are some old exams from previous years (since 2017 the exams come with solutions): 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024,
• Please be aware that the topics covered in this course have changed several times over the years. Therefore, some questions in these exams don't match the content of this year's course.

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 and the exercises. As this is a discussion forum, feel free to also answer the questions of your colleagues.

Lecture Material

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

© 2025 DISCO, TIK, ETH Zurich | Imprint | Last updated: Wed, 19 Feb 2025 12:51.