Principles of Distributed Computing (FS 2023)

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, but you can find video recordings in moodle.
• Exercises organized by Karolis Martinkus
  • 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.

News

• There will be no lecture and no exercise session the first week of the semester (February 22), so the first lecture is on March 1.
• The reading task has been announced (Stone Age Distributed Computing by Emek and Wattenhofer)
• Bonus task submission site is now live.
• The lecture scheduled for May 10th, to be conducted by Prof. Wattenhofer, has been cancelled due to unforeseen health circumstances. The exercise sessions are thus also cancelled.
• The second exercise session on May 31st will not take place.

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 9
• First feedback: April 24
• First revision: May 1
• Second submission: May 28
• 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 9th will be considered for the sencond deadline of May 28.

Approved Bonus Tasks For Exam Practice

In the following Polybox folder you can find the bonus tasks that were accepted. You can use them to practice for the exam as they have a similar difficulty and scope to what you can expect in the exam.

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

Reading Task

This lecture also comes with a reading task. The students have to read and analyse the paper Stone Age Distributed Computing by Emek and Wattenhofer on their own. There will be a question in the exam based upon the paper.

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: Sun, 09 Jul 2023 22:01.