Overview. This course is an introduction to the theory of distributed algorithms. The topics covered include:
- Models of computing: precisely what is a distributed algorithm, and what do we mean when we say that a distributed algorithm solves a certain computational problem?
- Algorithm design and analysis: which computational problems can be solved with distributed algorithms, which problems can be solved efficiently, and how to do it?
- Computability and computational complexity: which computational problems cannot be solved at all with distributed algorithms, which problems cannot be solved efficiently, and why is this the case?
No prior knowledge of distributed systems is needed. A basic knowledge of discrete mathematics and graph theory is assumed, as well as familiarity with the basic concepts from undergraduate-level courses on models on computation, computational complexity, and algorithms and data structures.
The course is worth 5 credits. This is an advanced course, suitable for MSc and PhD students—it is expected that the participants have a BSc degree in computer science (or equivalent). Lectures and course material will be in English.
Material. The course follows a short online textbook that is freely available for download. Lecture slides will be posted here on MyCourses.
Grading. There are two midterm exams (worth 60 + 60 points) plus exercises (worth 60 points). You can get at most 180 points in total. 90 points will be needed to pass the course (grade 1/5), and 150 points will be needed for the highest grade 5/5. Please see the "Assignments" page for more details on the exercises and how they are graded.
Format. The course is worth 5 credits, and there are 12 full weeks of lectures plus two exams. As one credit entails approx. 27 hours of work, you are expected to work 10–11 hours each week on this course. During the full lecture week x, the suggested weekly routine is as follows:
- Monday: 2 hours. Read chapter x. Have a look at the exercises.
- Tuesday: 2 hours. Lecture.
- Wednesday: 2 hours. Solve the first exercises of chapter x.
- Thursdays: 2 hours. Exercise session. Work together with the other students and try to find solutions to the more challenging exercises. Get help from the teaching assistant if needed.
- Friday: 2 hours. Finalise your solutions to the exercises and return them no later than next Monday.
It is recommended that you solve as many exercises as your weekly time budget of approx. 10–11 hours allows.
Learning objectives. The learning objectives of this course are as follows.
- Models of computing. You can define in a formally precise manner what is a distributed algorithm in each of the following models of distributed computing: PN model, LOCAL model, and CONGEST model, for both deterministic and randomised algorithms.
- Algorithm design and analysis. You can design distributed algorithms for each of these models, prove that your algorithm is correct, and analyse its running time.
- Computability and computational complexity. For a given graph problem, you can prove whether it can be solved at all in the PN model, and how long it takes to solve it in the PN and LOCAL models.
- Graph theory. You can recognise the standard graph-theoretic terms. You can prove connections between classical graph problems. You can prove and apply Ramsey's theorem.
The course exams will be designed to test these learning objectives. If you reach the learning objectives, you should be able to get the highest grade of 5/5.