Deterministic Distributed Algorithms


The intensive course on Deterministic Distributed Algorithms is offered 10–21 May 2010. The course meets daily from 12pm to 2pm. The course instructor is Jukka Suomela.

This is an advanced (Master level) course, so it is expected that the participants have a BSc degree (or equivalent). No specific courses are required – interest in algorithmic problems and a basic knowledge of discrete mathematics is sufficient (see below for more details).

The course is not based on any textbook. Presentation slides will be posted on this page, as well as pointers to additional material. All course material will be in English. Lectures are given in English, if there are foreigners present. The participants can write their report in Finnish or in English.

The volume of the course is 3 cr. There is no exam, and the grading is pass/fail. To pass the course, you are required to:

  1. take part in the lectures and exercise sessions (at least 6 times out of 9)
  2. write up your answers to all exercises, and return your report no later than at 6pm on Friday, 21 May 2010; the deadline is strict.

You can email the course instructor if you have any questions. If you use IRC, you can try to join the channel #dda-2010 on IRCnet (instructions).

Course content

The course covers selected topics in distributed computing; the focus is on deterministic distributed algorithms. The model of computation is the same as the one studied in the seminar course in autumn 2009; however, there is only a little overlap between the topics of the seminar and the topics of this course.

Lecture 1: Introduction

Lecture 2: Graph colouring and other algorithms with a log-star running time

Lecture 3: Basics of Ramsey theory

Lecture 4: Applications of Ramsey theory: lower-bound results and more

Lecture 5: Weak colouring and other algorithms with constant running time

Lecture 6: Exploration and rendezvous

Lecture 7: Local news

Course material

Lecture 0 (alternative version) last updated on 2010-05-19
Lecture 1 (alternative version) last updated on 2010-05-19
Lecture 2 (alternative version) last updated on 2010-05-19
Lecture 3 (alternative version) last updated on 2010-05-19
Lecture 4 (alternative version) last updated on 2010-05-19
Lecture 5 (alternative version) last updated on 2010-05-19
Lecture 6 (alternative version) last updated on 2010-05-19
Lecture 7 (alternative version) last updated on 2010-05-19
Exercises last updated on 2010-05-17

Solutions to exercises:


Monday10 May:lecture 1room B222
Tuesday11 May:lecture 2room B222
Wednesday12 May:lecture 3room B222
Thursday13 May:holiday
Friday14 May:exercise session Iroom B222
Monday17 May:lecture 4room B222
Tuesday18 May:lecture 5room B222
Wednesday19 May:lecture 6room D122
Thursday20 May:exercise session IIroom B222
Friday21 May:lecture 7room B222
return your report by 6pm

The lectures and exercise sessions are held in the Exactum building, from 12:15 to 14:00. The course schedule is available for download in iCalendar format.

Before the first lecture

It is recommended that the participants review the definitions of the following terms before the first lecture:


There are 5 exercises, and they are related to the topics covered in lectures 1–5. The exercises are announced on this web page beforehand.

The exercise sessions are reserved for discussing exercises, presenting solution ideas, and asking for advice. Session I focuses on exercises 1–3 and session II focuses on exercises 3–5. You should have made a serious attempt to solve the exercises before the exercise session, but you do not need to have solutions to all exercises available by then.

In your final report you must have a solution to all exercises (except those that are marked "optional"). You are welcome to ask questions and learn from other participants during the exercise sessions. You can also use any other sources, such as textbooks and original scientific articles. However, your final report must be self-contained (with full proofs of all claims that you make), you must disclose all sources that you used (by using appropriate citations, just like in any scientific writing), and naturally everything must be written by yourself, in your own words.

Your report should be easy to read. You should prepare it by using an appropriate typesetting software such as Latex – hand-written reports are not accepted. Email your report to the course instructor as a PDF file. No specific style is required – for example, you can use “article” or “amsart” style in Latex. You do not need to write an introduction or anything else besides your answers to the exercises; you can assume that the reader has taken the same course.

Please note that many of the exercises are open-ended: there is no single correct answer. You do not need to give the best known answer; it is sufficient to give a slightly weaker answer that is reasonably easy to prove.