### CS-E4510 - Distributed Algorithms, 10.09.2019-12.12.2019

Credits: 5

Schedule: 10.09.2019 - 12.12.2019

Contact information for the course (applies in this implementation):

The lectures are given by Jukka Suomela and the teaching assistants are Alkida Balliu and Dennis Olivetti.

Teaching Period (valid 01.08.2018-31.07.2020):

I - II (Autumn)

Learning Outcomes (valid 01.08.2018-31.07.2020):

After this course, you will be able to design and analyse efficient distributed algorithms for many different kinds of 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. You will be able to use reductions between computational problems in the context of distributed computing, construct covering relations between graphs in order to prove impossibility results, and apply Ramsey’s theorem to prove lower bounds on distributed time complexity.

Content (valid 01.08.2018-31.07.2020):

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 extremely large networks, as well as fundamental impossibility results that set limits to distributed computing.

Details on the course content (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 randomised algorithms.
• Algorithm design and analysis. You can design distributed algorithms for each of these models, prove that your algorithm is correct, and analyse 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 recognise the standard graph-theoretic terms. You can prove connections between classical graph problems. You can prove and apply Ramsey's theorem.

Assessment Methods and Criteria (valid 01.08.2018-31.07.2020):

Exams and exercises.

Elaboration of the evaluation criteria and methods, and acquainting students with the evaluation (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 are supposed to answer a quiz (2 points) and solve three exercises (3×2 points). If you solve all regular exercises correctly, you can get at most 96 points in total. 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

Details on calculating the workload (applies in this implementation):

The workload is approx. 10 hours per week. During the full lecture week x, the weekly routine is as follows:

• Tuesday: 2 hours. Lecture.
• Wednesday: 2 hours. Solve one exercise.
• Thursdays: 2 hours. Exercise session.
• Friday: 2 hours. Solve two exercises.

Study Material (valid 01.08.2018-31.07.2020):

Available online.

Details on the course materials (applies in this implementation):

The course follows a short online textbook that is freely available for download.

Substitutes for Courses (valid 01.08.2018-31.07.2020):

ICS-E5020 Distributed Algorithms

Prerequisites (valid 01.08.2018-31.07.2020):

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.