### CS-E4510 - Distributed Algorithms D, 08.09.2020-10.12.2020

Please note! Course description is confirmed for two academic years (1.8.2018-31.7.2020), which means that in general, e.g. Learning outcomes, assessment methods and key content stays unchanged. However, via course syllabus, it is possible to specify or change the course execution in each realization of the course, such as how the contact sessions are organized, assessment methods weighted or materials used.

#### LEARNING OUTCOMES

After this course, you will be able to design and analyse efficient distributed algorithms for problems that are related to computer networks and other distributed systems. You will also know how to prove that your algorithm is as fast as possible, i.e., the same problem cannot be solved faster with any distributed algorithm.

Credits: 5

Schedule: 08.09.2020 - 10.12.2020

Teacher in charge (valid 01.08.2020-31.07.2022): Jukka Suomela

Teacher in charge (applies in this implementation): Jukka Suomela

Contact information for the course (valid 20.08.2020-21.12.2112):

Our primary communication channel is Slack — if you have any questions, please try to ask our course staff there! If you have difficulties joining Slack or for some other reason it does not work for you, please email Jukka Suomela.

CEFR level (applies in this implementation):

Language of instruction and studies (valid 01.08.2020-31.07.2022):

Teaching language: English

Languages of study attainment: English

##### Content
• Valid 01.08.2020-31.07.2022:

This course provides an introduction to the theory of distributed algorithms. The topics include algorithmic techniques that can be used to solve graph problems efficiently in very large networks, as well as fundamental impossibility results that set limits to distributed computing.

• Applies in this implementation:

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.

##### Assessment Methods and Criteria
• Valid 01.08.2020-31.07.2022:

Exams and exercises.

• Applies in this implementation:

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.

• Applies in this implementation:

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.

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 lecture. Finish reading the lecture notes.
• Wednesday: 1–2 working hours. Solve one exercise.
• Thursdays: 2 working hours. Take part in the exercise session.
• Friday: 2–3 working hours. Solve two exercises.

#### DETAILS

##### Study Material
• Valid 01.08.2020-31.07.2022:

Available online.

• Applies in this implementation:

All course material will be made freely available online. We will have both written lecture notes (one chapter per week) and short prerecorded lecture videos (at least one short video per week).

##### Prerequisites
• Valid 01.08.2020-31.07.2022:

Bachelor's degree in computer science (or equivalent). No prior knowledge of distributed systems is needed, but students are expected to have an interest in algorithmic problems and a basic knowledge of discrete mathematics.

##### SDG: Sustainable Development Goals

9 Industry, Innovation and Infrastructure

#### FURTHER INFORMATION

##### Details on the schedule
• Applies in this implementation:

The weekly 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.