News

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!

Summary

This course is an introduction to the theory of distributed algorithms. The topics covered include:

• Models of computing: precisely what is a distributed algorithm, and what do we mean when we say that a distributed algorithm solves a certain computational problem?
• Algorithm design and analysis: which computational problems can be solved with distributed algorithms, which problems can be solved efficiently, and how to do it?
• Computability and computational complexity: which computational problems cannot be solved at all with distributed algorithms, which problems cannot be solved efficiently, and why is this the case?

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.

Material

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:

• week 1: slides · updated on 2014-09-09
• week 2: slides · updated on 2014-09-19
• week 3: slides · updated on 2014-09-23
• week 3: puzzles · updated on 2014-09-23
• week 4: slides · updated on 2014-09-30
• week 5: slides · updated on 2014-10-07
• week 6: slides · updated on 2014-10-12
• week 6: animation · updated on 2014-10-08
• week 7: slides · updated on 2014-10-28
• week 8: slides · updated on 2014-11-04
• week 9: slides · updated on 2014-11-11
• week 10: slides · updated on 2014-11-18
• week 11: slides · updated on 2014-11-25
• week 12: slides · updated on 2014-12-02

Additional reading (not part of this course):

• Week 3: Diestel: Graph Theory · a textbook freely available for online viewing
• week 8: covering maps in topology and graph theory · Wikipedia
• week 10: Ramsey theory and Ramsey’s theorem · Wikipedia

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

Grading

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!

Exercises

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:

• 0.5 points: at least 2 exercises with good solutions
• 1.0 points: at least 3 exercises with good solutions.

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

• On paper: Put your solutions in the course mailbox, which is a big white mailbox on the left side of room B336. Other courses are using the same mailbox, so write the name of the course very clearly!
• By email: Send your solutions to the teaching assistant.

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.

Format

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:

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.

• Models of computing. You 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 analysis. You can design distributed algorithms for each of these models, prove that your algorithm is correct, and analyse its running time.
• Computability and computational complexity. 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 theory. You can recognise the standard graph-theoretic terms. You can prove connections between classical graph problems. You can prove and apply Ramsey's theorem.

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.

Glossary