News

Please note that all information here is related to autumn 2015. You can find the web pages of autumn 2016 in MyCourses.

This course is now over for autumn 2015. The grading is available in MyCourses, and I have also prepared a summary of the course feedback, with my comments on it.

Summary

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

Basic course information is available in MyCourses.

The course follows a short online textbook that is freely available for download.

Lecture slides and other material from the lectures:

• week 1: slides · updated on 2015-09-08
• week 2: slides · updated on 2015-09-15
• week 3: slides · updated on 2015-09-22
• week 4: slides · updated on 2015-09-29
• week 5: slides · updated on 2015-10-06
• week 6: slides · updated on 2015-10-13
• week 6: animation · updated on 2014-10-08
• week 7: slides · updated on 2015-10-27
• week 8: slides · updated on 2015-11-03
• week 9: slides · updated on 2015-11-10
• week 10: slides · updated on 2015-11-17
• week 11: slides · updated on 2015-11-24
• week 12: slides · updated on 2015-12-01

Additional reading (not part of this course):

• week 3: Diestel: Graph Theory · a textbook freely available for online viewing
• week 8: covering maps in topology and graph theory · Wikipedia
• week 10: Ramsey theory and Ramsey’s theorem · Wikipedia

Examples of old exams:

• 1st mid-term: October 2014
• 2nd mid-term: December 2014
• final: February 2015

Model solutions for selected exercises will be made available in MyCourses after the exercises have been graded. You can see the web page of the previous iteration of the course for old lecture slides.

Grading

There are two midterm exams. For each half of the course, there are two grading options. Both options are always used automatically, and your final score is the maximum of the two.

1. Exercises and exam:
   • At most 24 points from the midterm exam.
   • At most 6 × 1 points from the weekly exercises.
2. Exam only:
   • At most 24 points from the midterm exam.
   • Points are multiplied by 1.25.

Therefore you can get at most 30 + 30 = 60 points in total. Approximately 30 points will be needed to pass the course (grade 1/5), and approximately 50 points will be needed for the highest grade 5/5.

Exercises

In the textbook, there are at least 5 exercises in each chapter. During lecture week x, you can solve any number of exercises in chapter x, and return them to the teaching assistant for grading.

You will earn points each week as follows:

• 0.5 points: at least 2 exercises with good solutions
• 1.0 points: at least 3 exercises with good solutions.

Here a “good solution” is readable, understandable, mostly correct, and returned on time.

The deadline for returning exercises of chapter x is Monday after lecture week x, before midnight. You can return your solutions either on paper or by email (handwritten notes are fine):

• On paper: Put your solutions in the course mailbox, which is a big white mailbox on the left side of room B336. Other courses are using the same mailbox, so write the name of the course very clearly!
• By email: Send your solutions to the teaching assistant.

The deadlines are strict. In case of illness, please get a doctor’s certificate and contact the lecturer ASAP. If you know that you will be e.g. travelling, please contact the lecturer well in advance.

In this course, you can work together with other students in order to solve the exercises. During the exercise session, there are plenty of opportunities to get help from your fellow students and also from the teaching assistant. This is permitted and encouraged. However, you must write up your solution by yourself, completely in your own words. The best approach is that you brainstorm with other students to come up with a solution idea, but then each of you works by yourself to write it up and fill in the details.

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:

It is recommended that you solve as many exercises as your weekly time budget of approx. 10–11 hours allows.

Lectures will be interactive. Exercise sessions will focus on solving exercises in small groups. Both are recommended but not compulsory; your grade does not depend on your participation in the lectures and exercise sessions.

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.

The following table gives a rough overview of how the learning objectives are divided between the two halves of the course. This will also give you an idea of which learning objectives are tested in the 1st exam, and what is left for the 2nd exam. Naturally, in the 2nd exam you should be prepared to demonstrate that you have reached all learning objectives.

Glossary