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?

    PREREQUISITES

    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). We will assume that the students have completed the course Introduction to Mathematical Reasoning for Computer Scientists. We will assume that you are comfortable with reading and writing mathematical proofs, and we will also assume familiarity with the basic concepts from undergraduate-level courses on models on computation, computational complexity, and algorithms and data structures.

    WORKLOAD

    The course is worth 5 credits, and there are 6 weeks of lectures plus one exams. As one credit entails approx. 27 hours of work, you are expected to work 21–22 hours each week on this course.

    MATERIAL

    We will follow the free online textbook called Distributed Algorithms 2020 that we have written for this course. For each chapter there are 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. Please watch the videos before each lecture!

    SCHEDULE OVERVIEW

    The course arrangement vary a bit from week to week (see below for details), but the high-level idea is this:

    • Tuesday, by 16.15: watch the videos of the relevant chapters before the lecture
    • Tuesday, at 16.15: deadline for submitting exercises of Chapters x−2 and x−1
    • Tuesday, at 16.15–18.00: lecture
    • Wednesday, at 10.15: deadline for Quiz x
    • Wednesday, at 10.15–12.00: exercise session, focus on exercises of Chapter x
    • Thursday, by 14.15: watch the videos of the relevant chapters before the lecture
    • Thursday, at 14.15–16.00: lecture
    • Friday, at 12.15: deadline for Quiz x+1
    • Friday, at 12.15–14.00: exercise session, focus on exercises of Chapter x+1

    8 LECTURES

    There will be 8 lectures, which correspond to textbook chapters as follows:

    • Tuesday, October 22, at 16.15–18.00 in hall T3: Chapters 1–2
    • Thursday, October 24, at 14.15–16.00 in hall U9: Chapters 3–4
    • (no lectures on October 29 and 31)
    • Tuesday, November 5, at 16.15–18.00 in hall T3: Chapter 5–6
    • Thursday, November 7, at 14.15–16.00 in hall U9: reflections on Chapters 1–6
    • Tuesday, November 12, at 16.15–18.00 in hall T3: Chapters 7–8
    • Thursday, November 14, at 14.15–16.00 in hall U9: Chapters 9–10
    • (no lectures on November 19 and 21)
    • Tuesday, November 26, at 16.15–18.00 in hall T3: Chapters 11–12
    • Thursday, November 28, at 14.15–16.00 in hall U9: reflections on Chapters 7–12

    Before each lecture, you are expected to have watched the short videos of the chapters that we will cover in the lecture!

    11 EXERCISE SESSIONS

    There will be 11 exercise sessions; these are an opportunity for you to solve exercises together with other students, and to get help for solving exercises:

    • Wednesday, October 23 at 10.15–12.00 in room TU5: focus on Chapters 1–2
    • (no exercise session on October 25)
    • Wednesday, October 30 at 10.15–12.00 in room TU5: focus on Chapter 3
    • Friday, November 1 at 12.15–14.00 in room TU3: focus on Chapter 4
    • Wednesday, November 6 at 10.15–12.00 in room TU5: focus on Chapter 5
    • Friday, November 8 at 12.15–14.00 in room TU3: focus on Chapter 6
    • Wednesday, November 13 at 10.15–12.00 in room TU5: focus on Chapter 7
    • Friday, November 15 at 12.15–14.00 in room TU3: focus on Chapter 8
    • Wednesday, November 20 at 10.15–12.00 in room TU5: focus on Chapter 9
    • Friday, November 22 at 12.15–14.00 in room TU3: focus on Chapter 10
    • Wednesday, November 27 at 10.15–12.00 in room TU5: focus on Chapter 11
    • Friday, November 29 at 12.15–14.00 in room TU3: focus on Chapter 12

    12 QUIZZES

    There is one quiz per chapter. The deadlines of the quizzes are on Wednesdays and Fridays, right before the exercise sessions:

    • Wednesday, October 23 at 10.15: Quiz 1
    • Friday, October 25, at 12.15: Quiz 2
    • Wednesday, October 30 at 10.15: Quiz 3
    • Friday, November 1 at 12.15: Quiz 4
    • Wednesday, November 6 at 10.15: Quiz 5
    • Friday, November 8 at 12.15: Quiz 6
    • Wednesday, November 13 at 10.15: Quiz 7
    • Friday, November 15 at 12.15: Quiz 8
    • Wednesday, November 20 at 10.15: Quiz 9
    • Friday, November 22 at 12.15: Quiz 10
    • Wednesday, November 27 at 10.15: Quiz 11
    • Friday, November 29 at 12.15: Quiz 12

    Each quiz is worth 2 points, and hence you can get up to 24 points in total by solving quizzes. The quizzes are automatically graded, and each wrong attempt costs you 0.5 points (so you will get 2.0, 1.5, 1.0, 0.5, or 0.0 points depending on how many attempts it took to get the correct answer). Late submissions are not accepted—if you miss the deadline, you will not get 0 points.

    2 × 12 EXERCISES

    In the textbook, there are 12 chapters, and in each chapter there are at least five exercises. You will need to solve two exercises from each chapter, and submit solutions following this schedule:

    • Tuesday, October 29, at 16.15: 2 + 2 exercises from Chapters 1–2
    • Tuesday, November 5, at 16.15: 2 + 2 exercises from Chapters 3–4
    • Tuesday, November 12, at 16.15: 2 + 2 exercises from Chapters 5–6
    • Tuesday, November 10, at 16.15: 2 + 2 exercises from Chapters 7–8
    • Tuesday, November 26, at 16.15: 2 + 2 exercises from Chapters 9–10
    • Tuesday, December 3, at 16.15: 2 + 2 exercises from Chapters 11–12

    Each exercise is worth 3 points, and hence you can get up to 72 points in total by solving exercises. The exercises are graded by a human being, using the scale 0–3. Late submissions are not accepted—if you miss the deadline, you will not get 0 points.

    1 EXAM

    There is an exam on Thursday, December 5, at 9.00–12.00. You can bring with you a single A4-sized double-sided cheatsheet, with any content of your choice, but no other material. The grading of the exam uses the scale pass/borderline/fail. If you get a grade "borderline" in the exam, you can attend an additional oral exam, and if you do sufficiently well in the oral exam, your exam grade will be upgraded to "pass". You need to get a "pass" in the exam (either directly or through the upgrade route) in order to be able to pass the course.

    GRADING

    The grading scale is as follows:

    • grade 1/5: pass the exams
    • grade 2/5: pass the exams + at least 20 points from exercises and quizzes
    • grade 3/5: pass the exams + at least 40 points from exercises and quizzes
    • grade 4/5: pass the exams + at least 60 points from exercises and quizzes
    • grade 5/5: pass the exams + at least 80 points from exercises and quizzes

    CHALLENGING EXERCISES

    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 exam). The challenging exercises will not give regular points for course grading, but they will give you challenge points. If you get enough regular points for grade 5/5 and you are among the top-3 students in the challenge points, you will get a personal certificate as a recognition for the achievement.

    COLLABORATION 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. The use of AI tools is comparable to asking a friend: you can use them to get solution ideas but you cannot use them to write answers for you.

    COURSE STAFF

    The course is lectured by Jukka Suomela, and the exercise sessions are organized by Massimo Equi.

    ONLINE TOOLS

    Our primary communication platform is the Zulip discussion forum at da2024.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.

    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 exam will be designed to test these learning objectives.