ICS-E5020 Distributed Algorithms

Autumn 2014

Department of Information and Computer Science
Aalto University

News Summary Material Grading Exercises Format Objectives Glossary


This course is offered in autumn 2014; see Noppa for more details on the schedule. The course instructor is Jukka Suomela, and the teaching assistant is Juho Hirvonen—feel free to contact us by email if you have any questions!


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

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):

Model solutions for selected exercises will be made available in Noppa after the exercises have been graded.


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 2 × 24 points from the two course exams.
    • At most 12 × 1 points from the weekly exercises.
  2. Exam only:
    • At most 2 × 24 points from the course exams.
    • Points are multiplied by 1.25.

You will get at most 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.

Update: Based on the feedback, we will experiment with a bit more flexible and student-friendly grading scheme during the 2nd half of the course. See the news in Noppa for deatails!


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:

Monday2 hoursRead Chapter x. Have a look at the exercises.
Tuesday2 hoursLecture.
Wednesday2 hoursSolve the first exercises of Chapter x.
Thursdays2 hoursExercise 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.
Friday2 hoursFinalise 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.

Learning Objectives

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.

Objective1st period
(Chapters 1–6)
2nd period
(Chapters 7–12)
Models of computingYou 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 analysisYou 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 theoryYou can recognise the standard graph-theoretic terms. You can prove connections between classical graph problems.You can prove and apply Ramsey's theorem.


node, vertexsolmu
regular graphsäännöllinen verkko
spanning subgraphvirittävä aliverkko
induced subgraphindusoitu aliverkko
connected componentyhtenäinen komponentti
radius-r neighbourhoodr-säteinen ympäristö
connected graphyhtenäinen verkko
independent setriippumaton joukko
vertex coversolmupeite
dominating setdominoiva joukko
edge coverkaaripeite
edge dominating setdominoiva kaarijoukko
maximal independent setmaksimaalinen riippumaton joukko
maximum independent setmaksimikokoinen riippumaton joukko,
suurin riippumaton joukko
minimal vertex coverminimaalinen solmupeite
minimum vertex coverminimikokoinen solmupeite,
pienin solmupeite
domatic partitiondomaattinen ositus
edge colouringkaariväritys
edge domatic partitiondomaattinen kaariositus
bipartite graphkaksijakoinen verkko
perfect matchingtäydellinen pariutus
directed graphsuunnattu verkko
undirected graphsuuntaamaton verkko
distributed algorithmhajautettu algoritmi
distributed computinghajautettu laskenta
distributed systemhajautettu järjestelmä
deterministic algorithmdeterministinen algoritmi
randomised algorithmsatunnaisalgoritmi
approximation algorithmapproksimointialgoritmi
approximation factorapproksimointisuhde
covering mappeitekuvaus
local neighbourhoodpaikallinen ympäristö
edge packingkaaripakkaus