Deterministic Distributed Algorithms

News · Summary · Content · Material · Schedule · Format · Grading · Tracking · Support · Feedback · Comments · More · FAQ · Glossary

Latest news


The course on Deterministic Distributed Algorithms is offered in Spring 2012, during the 4th period. The course instructor is Jukka Suomela, and the exercise sessions are held by Juho Hirvonen.

The course provides an introduction to the theory of distributed algorithms. The topics include algorithmic techniques that can be used to solve graph problems efficiently in extremely large networks, as well as fundamental impossibility results that set limits to distributed computing. No prior knowledge of distributed systems is needed, but students are expected to have an interest in algorithmic problems and a basic knowledge of discrete mathematics.

The course is worth 4 credits, and the course code is 582661. This is an advanced (Master level) course, so it is expected that the participants have a BSc degree or equivalent.

The course is not based on any textbook; course material and presentation slides will be posted on this page. Lectures and course material will be in English.

Course content

The course is an extended version of the intensive course that was given in spring 2010.

The main themes and the learning objectives are as follows. In the course exam, if you can do everything listed in the column "Approaches learning objectives", you should be able to pass the course, and if you can do everything listed in the column "Reaches learning objectives", you should be able to get the highest grade 5/5.

Principal theme Prerequisite knowledge Approaches learning objectives Reaches learning objectives Deepens learning objectives
Graph-theoretic foundations
(Chapter 1)
basics of discrete mathematics apply the definitions of graph-theoretic concepts prove connections between graph problems apply techniques beyond elementary graph theory
Port-numbering model
(Chapters 2 & 4)
basic knowledge of models of computation design simple distributed algorithms analyse distributed algorithms apply linear programming to design combinatorial algorithms
Impossibility results
(Chapters 3 & 4)
basics of discrete mathematics identify covering relations between graphs construct graphs that can be used to prove negative results derive tight inapproximability results
Unique identifiers
(Chapter 5)
basics of discrete mathematics describe a fast graph colouring algorithm and prove its correctness use graph colouring as an algorithm design technique describe modern graph colouring algorithms
Ramsey theory
(Chapter 6)
basics of discrete mathematics apply Ramsey's theorem to prove negative results prove Ramsey's theorem apply bounds on Ramsey numbers to prove lower bounds

Course material

The course material is a short online textbook that is freely available for download:

Additional material:


Course registration opened on 21 February 2012 in the Ilmo system.

Lectures are given on

The exercise sessions are held on

The first lecture is on Tuesday, 13 March 2012, and the first exercise session is on 16 March. There is an Easter holiday from 5 April to 11 April. The last lecture is on Thursday, 26 April, and the last exercise session is on 27 April.

There is a course exam on 4 May 2012, and a renewal exam on 15 June 2012 (check the exam web pages for the latest information).

The course schedule is available on Google Calendar: html, ical, xml.


The course is worth 4 credits, and there are 6 full weeks of lectures plus an exam. As one credit entails approx. 27 hours of work, you are expected to work 17–18 hours each week on this course.

The emphasis is on self-study; you will learn by doing. The lectures and exercise sessions are intended to support self-study, not replace it.

The course material consists of 6 short chapters of text, and with each chapter there is a selection of exercises. On week x you are expected to do the following:

Note that you are not expected to solve all exercises. Keep track of your working hours – do not overdo it. Usually, it makes sense to start with the first exercises. However, you are welcome to skip exercises that look utterly trivial to you, and focus on more interesting problems. If you get stuck, remember that help is available almost daily.

Below is the suggested weekly routine. You are free to adapt it to your needs, but keep in mind that the lectures and exercise sessions are planned so that they support this routine. In particular, make sure that you have read the relevant chapter of the course material before Tuesday's lecture.

Mon4 hoursself-studyRead Chapter x, have a look at the exercises.
Tue2 hourslecturesReview of Chapter x. Discussion. Examples.
2 hoursself-studyExercises.
Wed3 hoursself-studyExercises. Update course tracking.
Thu2 hourslecturesMore in-depth material related to Chapter x. We will discuss possible solutions to selected exercises.
2 hoursself-studyExercises. Update course tracking.
Fri2 hoursexercise
Model solutions to selected exercises, discussion. Update course tracking.

The lectures and exercise sessions will be adapted based on the information in the course tracking system. Hence to make sure that the sessions are as useful to you as possible, remember to update the course tracking system regularly.

The beginning of the first week will be a bit more relaxed, as the material focuses on reviewing concepts from graph theory. Hence if you are only reading these instructions after the first lecture, you will still have time to catch up. However, do not expect that the exercises of the first week are trivial…

If you realise that you have taken too many courses during the 4th period, remember that you can abuse the Easter holiday for load balancing. There will be one full week without any lectures or exercise sessions in April.

Grading and requirements

The grading is based solely on the course exam, using the usual scale of 1–5. If you pass the exam, you pass the course – there are no other requirements.

In particular, you will not get any credits or points from the exercises. However, most probably

For an average student, 4 × 27 hours of studying during the course will be sufficient in order get an average grade in the exam.

Course tracking

There is an online course tracking system. In the system, you are expected to report your progress. All reports are anonymous.

The course tracking system serves the following purposes:

In the course tracking system, you will report your progress with each exercise using the following codes:

AThe problem looks straightforward. I did not solve it but I am confident that I would be able to solve it in the exam.
BI solved the problem by myself and I believe the solution is correct. I am confident that I would be able to solve it in the exam.
CI needed some help from other students or course instructors, but I believe I have a correct solution now and I understand all parts of it. I am confident that I would be able to solve this problem in the exam.
DI have tried hard, but I do not have a correct solution yet. I need some help.
EI am still working on it…
XI will not have time to solve this problem, as I have already spent approx. 18 hours/week on this course.
(empty)I have not yet had a look at it.

If you have registered for the course, you should have received detailed information by email; if this is not the case, please contact the course instructor.

Online support

The following online forums are available:

You do not need to follow these forums; all essential information will be provided on this web page. Nevertheless, it might be a good idea to join the Google Groups forum or try out IRC well in advance before the course begins, just in case you should need quick help with the exercises.

You can also email Jukka Suomela or Juho Hirvonen if you have any questions!

Course feedback

If you have any comments or suggestions before or during the course, feel free to email the course instructor or drop a note on the online forums.

After the course, everyone is expected to submit course feedback using the course feedback system. Course feedback is anonymous.

I will publish a summary of the course feedback on this web page, and I will also comment on it here.

Comments on course and feedback

The key statistics of the course are as follows:

The following table summarises the numerical course feedback (scale from 1 = disagree to 5 = agree).

Course objectives were clear ·2·444555555
Course material supported learning ··3444555555
Course activities supported learning ··3344445555
Exams and grading measured learning ··34444555
Lots of work ·2334555555
Overall ··3344455555

Here are selected (adapted, abbreviated, translated, and anonymised) fragments of the free-form course feedback, both from the feedback form and from the emails that I received.

First of all, many thanks to all of you who provided feedback, and in particular, thanks for your kind, supportive, and helpful comments! I really appreciate all kinds of feedback.

Here are my own interpretations of the main points of the feedback, with some comments:

I would like to comment the last point – workload – in more detail. Let us first have a look at the background. The Finnish legislation (Valtioneuvoston asetus yliopistojen tutkinnoista 794/2004, 5 §) explicitly states that one full year of studies equals 1600 working hours, which equals 60 credits; many other European countries have a very similar system.

Please note that I as a course instructor cannot really change any of this. In any case, 1600 hours per year sounds like a very reasonable number to me. For example, if you do 40 hours of studies each week, you can enjoy 12 full weeks of holidays each year.

Now if we do the math, we conclude that a 4-credit course entails approximately 107 hours of studies. Even if we allocate some working hours for the exam, we will have approximately 100/6 ≈ 17 hours of studies each week during a 6-week lecture course. This number seemed to come as a surprise to most of the students.

Unfortunately, this just happens to be the way our system works; I did not make up the numbers. Of course I could organise a course that is worth only 2 credits, and then I would expect only approximately 8 hours of studies each week, but I am not sure if the students would be happy with this approach, either.

I will try to provide some words of general advice, though. Please note that the total length of the four teaching periods is only 28 weeks, including the exam weeks. The idea is not that you compress a full working year in just 28 weeks! If you tried to do that, you would certainly be in trouble, struggling with 60-hour weeks. A simple solution is to study on your own outside the usual teaching periods – this way you can enjoy relaxed 40-hour working weeks, yet you will still have a long summer holiday.

I hope this at least clarifies the situation, even if it does not actually help that much with the workload… Once again, many thanks to all of you for taking part in the course! Have a nice summer!

Further studies

There will be a seminar course on distributed algorithms in autumn 2012.

Master's thesis topics are available from the course instructor.


Can I take this course if I already took the 2010 version?
For all administrative purposes, these are the same course. They have the same course code, and you cannot have more than one instance of it in your degree. Of course nothing prevents you from re-doing the course.
How to draw graphs?
All illustrations in the course material, slides, etc. were created with OmniGraffle. Unfortunately, it is only available for Mac OS X, and it is commercial software. If you are looking for free, open-source software for Linux, I am not aware of anything that I could honestly recommend. Windows users might want to have a look at Microsoft Visio.


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