Allmänt
OVERVIEW
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
The course follows a short online textbook that is freely available for download. Lecture slides will be posted here on MyCourses.
GRADING
There are two midterm exams that check that you have reached the learning objectives of the course (see below). The grading of the exams is pass/fail. To pass the course, you will have to pass both of the exams.
There are also weekly exercises. Each week you can get at most 8 points in total from the regular exercises (see below). If you solve all regular exercises correctly, you can get at most 96 points in total. On top of that, you can also get extra points from the challenging exercises. The grading scale is as follows:
- grade 1/5: pass both of the midterm exams
- grade 2/5: pass both of the midterm exams + at least 20 exercise points
- grade 3/5: pass both of the midterm exams + at least 40 exercise points
- grade 4/5: pass both of the midterm exams + at least 60 exercise points
- grade 5/5: pass both of the midterm exams + at least 80 exercise points
COURSE STAFF
The lectures are given by Jukka Suomela and the teaching assistant is Alkida Balliu.
WORKLOAD
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.
SCHEDULE AND DEADLINES
During the full lecture week x, the weekly routine is as follows:
- Monday: 2 hours. Read chapter x. Answer the quiz.
- Tuesday: 2 hours. Lecture.
- Wednesday: 2 hours. Solve one exercise.
- Thursdays: 2 hours. Exercise session.
- Friday: 2 hours. Solve two exercises.
Each week you are supposed to answer a quiz (2 points) and solve three exercises (3×2 points). In the textbook, there are at least five exercises in chapter x; you can freely choose which of those you solve during week x, and in which order. The deadlines are as follows:
- Tuesday at noon: Answer the weekly quiz in MyCourses.
- Wednesday at midnight: Submit your solution to one exercise in MyCourses.
- Friday at midnight: Submit your solutions to two other exercises in MyCourses.
The idea is that the quiz makes sure you have had a look at the relevant chapter before the lecture, and the Wednesday deadline makes sure that you have had a look at the exercises before the exercise session. In the exercise session, you will get help with solving the remaining two exercises.
The grading of the quiz and the exercises is 0/1/2. Late submissions are not accepted. However, please note that you can submit early if you want. If there are technical difficulties with MyCourses, please email your solution to the lecturer (the same deadlines apply).
RULES
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.
DISCUSSION FORUM
Here is a Slack discussion forum that you can use to chat with other students, or to get help with the exercises and the course material: aaltoda.slack.com.
You can create a user account using your Aalto email address at aaltoda.slack.com/signup/.
CHALLENGING EXERCISES
In the textbook, there are more challenging exercises that are marked with a star. You can solve those at any point during the course (before the second midterm exam). Each such problem is worth 4 extra points, and you can solve any number of those problems during the course. This is on top of the points that you get from the regular exercises. Please email your solution to the lecturer for grading; do not try to submit these via MyCourses.
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.