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 an introduction to the theory of distributed algorithms. The topics covered include:
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.
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:
Additional reading (not part of this course):
Examples of old exams:
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.
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.
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.
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:
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):
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.
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.|
|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.
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.
The learning objectives of this course are as follows.
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.
|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.||(Recap, more depth.)|
|Computability and computational complexity||(Informal introduction.)||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.|
|regular graph||säännöllinen verkko|
|spanning subgraph||virittävä aliverkko|
|induced subgraph||indusoitu aliverkko|
|connected component||yhtenäinen komponentti|
|radius-r neighbourhood||r-säteinen ympäristö|
|connected graph||yhtenäinen verkko|
|independent set||riippumaton joukko|
|dominating set||dominoiva joukko|
|edge dominating set||dominoiva kaarijoukko|
|maximal independent set||maksimaalinen riippumaton joukko|
|maximum independent set||maksimikokoinen riippumaton joukko,|
suurin riippumaton joukko
|minimal vertex cover||minimaalinen solmupeite|
|minimum vertex cover||minimikokoinen solmupeite,|
|domatic partition||domaattinen ositus|
|edge domatic partition||domaattinen kaariositus|
|bipartite graph||kaksijakoinen verkko|
|perfect matching||täydellinen pariutus|
|directed graph||suunnattu verkko|
|undirected graph||suuntaamaton verkko|
|distributed algorithm||hajautettu algoritmi|
|distributed computing||hajautettu laskenta|
|distributed system||hajautettu järjestelmä|
|deterministic algorithm||deterministinen algoritmi|
|local neighbourhood||paikallinen ympäristö|