Principles of Distributed Computing (FS 2024)
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 Roger Wattenhofer, 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
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:
- First submission: April 10
- First feedback: April 24
- First revision: May 1
- Second submission: May 29
- Second feedback: June 5
- Second revision: June 12
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
- 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.
- 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 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 |
Slides by S.Schmid, TU Berlin | ||
Chapter 6 Global Problems 27.03.2023 |
Script Video |
Supervised by Robin Exercises |
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
[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 |