Topic outline

  • CORONAVIRUS UPDATES

    The course will be organized this year 100% online! You can take part in all course activities (lectures, exercises, exams) remotely. The times of the lectures, exercise sessions, and exams announced here in MyCourses still hold, but everything is arranged online; please see below for the details. If you are interested in taking part in the course, please register in Oodi as usual, join our Slack workspace, and follow instructions there!

    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

    All course material will be made freely available online — see the Materials page here in MyCourses. We will have both written lecture notes (one chapter per week) and short prerecorded lecture videos (at least one short video per week).

    GRADING

    There are two midterm exams that check that you have reached the learning objectives of the course. 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, and 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

    In the lecture notes, there are additional 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 additional points, and you can solve any number of those problems during the course.

    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 from the teachers. 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.

    COURSE STAFF

    The co-teachers of the course are Jukka Suomela (primary contact) and Juho Hirvonen.

    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

    Well in advance before each week, we make the prerecorded videos and lecture notes available online. During each lecture week, the recommended weekly routine is as follows:

    • Monday: 1–2 working hours.
      • Watch the prerecorded videos.
      • Start to read the lecture notes.
      • Answer the quiz.
    • Tuesday: 2–3 working hours.
      • Take part in the online lecture (at 12:15pm–14:00pm).
      • Finish reading the lecture notes.
    • Wednesday: 1–2 working hours.
      • Solve one exercise.
    • Thursdays: 2 working hours.
      • Take part in the online exercise session (at 10:15am–12:00pm).
    • Friday: 2–3 working hours.
      • Solve two exercises.

    Each week you are supposed to answer a quiz (2 points) and solve three exercises (3×2 points). In the lecture notes, there are at least five exercises each week; you can freely choose which of those you solve, and in which order. The deadlines are as follows:

    • Tuesday at noon: Answer the weekly quiz in MyCourses. [For the first quiz there is extra time until midnight, but please try to complete the quiz by noon if possible. The will not be extensions in the other weeks.]
    • 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 at least watched the videos 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).

    The midterm exams will be take-home exams. The exam questions will be published here on MyCourses at least 24 hours before the end of the exam, and you will need to return your solutions through MyCourses by the end of the exam. After the exam, we will also have a one-to-one Zoom meeting with each student; in the meeting we will discuss your solutions, primarily to make sure they are your own work. If you cannot take part in the exam in the usual time frame, please be in touch with the course staff.

    ONLINE TOOLS

    Our primary communication platform is the Slack workspace at aaltoda2020.slack.com. We will use Slack to coordinate all course activities, including lectures and exercise sessions, and all participants are expected to follow Slack. In the Slack workspace, channel #general can be used for any kind of general discussions and questions related to the course. All important official announcements will be posted on channel #important. You can create a Slack user account at aaltoda2020.slack.com/signup/. Just enter your aalto.fi email address and follow the instructions. To make our life easier, we suggest that you set your real name correctly in your Slack profile. However, if you wish to remain anonymous on Slack, it is also possible — you can simply pick a random nickname and leave your real name unspecified.

    Prerecorded videos will be made available on YouTube and Panopto. Lecture notes, presentation slides, links to the videos, and other additional material will be posted here on MyCourses and also on Slack.

    We will use Zoom for lectures and exercise sessions. Zoom links and other practical information will be posted in Slack before the lecture starts.

    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 randomized algorithms.
    • Algorithm design and analysis. You can design distributed algorithms for each of these models, prove that your algorithm is correct, and analyze 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 recognize the standard graph-theoretic terms. You can prove connections between classical graph problems.

    The course exams will be designed to test these learning objectives.