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
  • 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.

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:

• First submission: April 10
• First feedback: April 24
• First revision: May 1
• Second submission: May 29
• Second feedback: June 5
• Second revision: June 12

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

• 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

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

© 2024 DISCO, TIK, ETH Zurich | Imprint | Last updated: Fri, 09 Aug 2024 09:48.