News

The grading of the course is now available in the intranet (including the renewal exam).

I will lecture an extended version of this course at Aalto University in autumn 2014.

Summary

The course on Deterministic Distributed Algorithms is offered in spring 2014, during the 4th period. The course instructor is Jukka Suomela, and the teaching assistant is Joel Rybicki.

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 follows a short online textbook that is freely available for download:

• A Course on Deterministic Distributed Algorithms

Presentation slides will be posted on this page. Lectures and course material will be in English.

Course content

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.

Material

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

• A Course on Deterministic Distributed Algorithms

Lecture slides:

• week 1 · updated on 2014-03-11
• week 2 · updated on 2014-03-20
• week 3 · updated on 2014-03-27
• week 4 · updated on 2014-04-03
• week 5 · updated on 2014-04-10
• week 6 · updated on 2014-04-24

Schedule

Registration for the course opened on 18 February 2014 in the Ilmo system.

Lectures are given on

• Tuesdays from 12:15 to 14:00 in room B222, and
• Thursdays from 12:15 to 14:00 in room B222.

The exercise group meets on

• Fridays from 12:15 to 14:00 in room B119.

The first lecture is on Tuesday, 11 March 2014, and the first exercise session is on Friday, 16 March 2014. There is an Easter holiday from 17 April to 23 April, so “lecture week 6” actually spans two calendar weeks. The last lecture is on Thursday, 24 April 2014, and the last exercise session is on 25 April 2014.

Format

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 course material consists of 6 short chapters of text, and for each chapter there is a selection of exercises. The course is heavily exercise-driven; you will learn by doing. The lectures and exercise sessions will be interactive—we will spend a lot of time working together and discussing possible solutions to exercises.

During the full lecture week x, the suggested weekly routine is as follows:

You are expected to return your solutions to 4 exercises for grading each week—see below for detailed instructions. However, it is highly recommended that you solve as many exercises as your weekly time budget of approx. 17–18 hours allows. In many cases, you will find that you can solve 4 exercises much faster. I picked the number 4 here so that you can do it even if you are temporarily overloaded with other courses during some weeks.

Grading

There are two grading options.

1. Exercises and exam:
   • Solve 4 exercise problems each week (at most 6 × 4 × 0.5 = 12 points).
   • Solve 4 problems out of 5 in the exam (at most 4 × 12 = 48 points).
2. Exam only:
   • Solve 5 problems out of 5 in the exam (at most 5 × 12 = 60 points).

The options are available as follows:

• Course exam: option 1 and option 2.
• First separate exam (renewal exam): option 1 and option 2.
• Other separate exams: option 2 only.

In each case, 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.

If both option 1 and option 2 are available, the grading of the exam is done in a maximally student-friendly manner. More precisely, all answers will be graded, and your final score T is calculated as follows:

• e = exercise points, scale 0–12, as a whole integer, rounded up
• p_i = grading of problem i in the exam, scale 0–12 (i = 1, 2, …, 5)
• S = p₁ + p₂ + … + p₅
• S_i = e + S − p_i
• T = max {S, S₁, S₂, …, S₅}

Exercises

In the course material, there are at least 6 exercises in each chapter.

During the full lecture week x, you will select 4 exercises from Chapter x, solve them, and return your solutions to the teaching assistant for grading. There are two possible ways to return your solutions:

1. No later than at 13:59 on the same Friday, during the exercise session, in person, on paper (handwritten solutions are fine).
2. No later than at 23:59 next Monday, by email to dda-2014@helsinki.fi, as a PDF file that is easy to read on a computer screen (computer typeset solutions are recommended but not necessary).

You can combine the two approaches if you wish. You can answer in English or in Finnish (see the glossary). For programming exercises, put your code e.g. on Github and email a link.

The details of the grading procedure are as follows:

• You will get 0.5 points for each solution that is readable, understandable, mostly correct, and returned on time according to one of the above procedures. For all other solutions you will get 0.0 points.
• If you choose to return more than 4 solutions, all of them will be graded. However, each week you can get at most 2.0 points in total.

The deadlines are strict. Deadline extensions are given only in case of an illness or for similar reasons; a doctor's certificate will be required.

Social media

For informal discussion related to the course, you can join the following Facebook group:

• https://www.facebook.com/groups/dda2014/

Alternatively you can use the IRC channel #dda-2014 on IRCnet for real-time chat.

You do not need to follow these forums. All essential information will be provided on this web page. There is no guarantee that you will get assistance through these forums; please contact the lecturer or the teaching assistant if you need help.

Glossary