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:
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).
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
|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:
|Monday||10 May:||lecture 1||room B222|
|Tuesday||11 May:||lecture 2||room B222|
|Wednesday||12 May:||lecture 3||room B222|
|Friday||14 May:||exercise session I||room B222|
|Monday||17 May:||lecture 4||room B222|
|Tuesday||18 May:||lecture 5||room B222|
|Wednesday||19 May:||lecture 6||room D122|
|Thursday||20 May:||exercise session II||room B222|
|Friday||21 May:||lecture 7||room 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.
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.