Topic outline

  • General

    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). The lectures and the course material will be in English.

    MATERIAL

    We will follow the free online textbook called Distributed Algorithms 2020 that we have written for this course. Each week we will cover one chapter of the book. Each week there is also one or two short videos that introduce you to the topic; you can find the links to the videos also in the same web site as the book.

    The book was thoroughly renewed for the 2020 edition of the course. There will be some minor updates to the material this year, but feel free to start to read the book and watch the videos!

    GRADING

    There are two exams that check that you have reached the learning objectives of the course, one at the end of period I and another at the end of period II. 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 exams
    • grade 2/5: pass both of the exams + at least 20 exercise points
    • grade 3/5: pass both of the exams + at least 40 exercise points
    • grade 4/5: pass both of the exams + at least 60 exercise points
    • grade 5/5: pass both of the exams + at least 80 exercise points

    In the textbook, there are additional challenging exercises that are marked with a star. You can solve those at any point during the course (before the second 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 sessions, 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 course is organized this year by Jukka Suomela (primary contact), Amirreza Akbari, and Sameep Dahal.

    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 each lecture week, the recommended weekly routine is as follows:

    • Monday: 1–2 working hours.
      • Watch the videos.
      • Start to read the chapter of the textbook.
      • Answer the quiz.
    • Tuesday: 2–3 working hours.
      • Take part in the lecture (at 12:15pm–14:00pm).
      • Finish reading the chapter.
    • Wednesday: 1–2 working hours.
      • Solve one exercise.
    • Thursdays: 2 working hours.
      • Take part in the 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 textbook, there are at least five exercises in each chapter; 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. There 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 you submit early and get feedback before the deadline, you can revise and resubmit. If there are technical difficulties with MyCourses, please email your solution to the lecturer (the same deadlines apply).

    BEFORE THE FIRST LECTURE

    • Read this web page completely.
    • Complete the course registration in Sisu as usual.
    • Join the Zulip discussion forum of our course, using your Aalto user name and password.
    • Follow discussions in Zulip, submit your solution to the first quiz, and then take part in the first lecture on September 6.

    ONLINE TOOLS

    Our primary communication platform is the Zulip discussion forum at da2022.zulip.aalto.fi. We will use Zulip to coordinate all course activities, and all participants are expected to follow Zulip. In the Zulip workspace, channel #general can be used for any kind of general discussions and questions related to the course. All important official information will be posted in the stream #important.

    The short prerecorded videos and the textbook are available in the Distributed Algorithms 2020 web site.

    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.