CSE4510  Distributed Algorithms D, Lecture, 22.10.20245.12.2024
Topic outline

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 undergraduatelevel 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 highlevel 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 19, 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 12, at 9.00–12.00. You can bring with you a single A4sized doublesided 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 top3 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 graphtheoretic terms. You can prove connections between classical graph problems.
The course exam will be designed to test these learning objectives.