Deterministic Distributed Algorithms

Spring 2014

Department of Computer Science
University of Helsinki

News Summary Content Material Schedule Format Grading Exercises Social media Glossary

News

The grading of the course is now available in the intranet (including the renewal exam).

I will lecture an extended version of this course at Aalto University in autumn 2014.

Summary

The course on Deterministic Distributed Algorithms is offered in spring 2014, during the 4th period. The course instructor is Jukka Suomela, and the teaching assistant is Joel Rybicki.

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

The course is worth 4 credits, and the course code is 582661. This is an advanced (Master level) course, so it is expected that the participants have a BSc degree or equivalent.

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

Presentation slides will be posted on this page. Lectures and course material will be in English.

Course content

The main themes and the learning objectives are as follows. In the course exam, if you can do everything listed in the column "Approaches learning objectives", you should be able to pass the course, and if you can do everything listed in the column "Reaches learning objectives", you should be able to get the highest grade 5/5.

Principal theme Prerequisite knowledge Approaches learning objectives Reaches learning objectives Deepens learning objectives
Graph-theoretic foundations
(Chapter 1)
basics of discrete mathematics apply the definitions of graph-theoretic concepts prove connections between graph problems apply techniques beyond elementary graph theory
Port-numbering model
(Chapters 2 & 4)
basic knowledge of models of computation design simple distributed algorithms analyse distributed algorithms apply linear programming to design combinatorial algorithms
Impossibility results
(Chapters 3 & 4)
basics of discrete mathematics identify covering relations between graphs construct graphs that can be used to prove negative results derive tight inapproximability results
Unique identifiers
(Chapter 5)
basics of discrete mathematics describe a fast graph colouring algorithm and prove its correctness use graph colouring as an algorithm design technique describe modern graph colouring algorithms
Ramsey theory
(Chapter 6)
basics of discrete mathematics apply Ramsey's theorem to prove negative results prove Ramsey's theorem apply bounds on Ramsey numbers to prove lower bounds

Material

The course material is a short online textbook that is freely available for download:

Lecture slides:

Schedule

Registration for the course opened on 18 February 2014 in the Ilmo system.

Lectures are given on

The exercise group meets on

The first lecture is on Tuesday, 11 March 2014, and the first exercise session is on Friday, 16 March 2014. There is an Easter holiday from 17 April to 23 April, so “lecture week 6” actually spans two calendar weeks. The last lecture is on Thursday, 24 April 2014, and the last exercise session is on 25 April 2014.

Format

The course is worth 4 credits, and there are 6 full weeks of lectures plus an exam. As one credit entails approx. 27 hours of work, you are expected to work 17–18 hours each week on this course.

The course material consists of 6 short chapters of text, and for each chapter there is a selection of exercises. The course is heavily exercise-driven; you will learn by doing. The lectures and exercise sessions will be interactive—we will spend a lot of time working together and discussing possible solutions to exercises.

During the full lecture week x, the suggested weekly routine is as follows:

Monday:You will read Chapter x.
Tuesday:Lecture. I will give a short presentation on Chapter x, covering the essential new material of this week. Then we will start working on exercises together.
Wednesday:You will work on your own, solving exercises.
Thursdays:Lecture. I will give another short presentation on Chapter x, covering more in-depth material. We will discuss exercises and possible solutions to them.
Friday:Exercise session. If you still have difficulties with the exercises, or if you are unsure about your solutions, this will be a good opportunity to get help with them. You will return your solutions to the exercises of Chapter x for grading.

You are expected to return your solutions to 4 exercises for grading each week—see below for detailed instructions. However, it is highly recommended that you solve as many exercises as your weekly time budget of approx. 17–18 hours allows. In many cases, you will find that you can solve 4 exercises much faster. I picked the number 4 here so that you can do it even if you are temporarily overloaded with other courses during some weeks.

Grading

There are two grading options.

  1. Exercises and exam:
  2. Exam only:
    • Solve 5 problems out of 5 in the exam (at most 5 × 12 = 60 points).

The options are available as follows:

In each case, you will get at most 60 points in total. Approximately 30 points will be needed to pass the course (grade 1/5), and approximately 50 points will be needed for the highest grade 5/5.

If both option 1 and option 2 are available, the grading of the exam is done in a maximally student-friendly manner. More precisely, all answers will be graded, and your final score T is calculated as follows:

Exercises

In the course material, there are at least 6 exercises in each chapter.

During the full lecture week x, you will select 4 exercises from Chapter x, solve them, and return your solutions to the teaching assistant for grading. There are two possible ways to return your solutions:

  1. No later than at 13:59 on the same Friday, during the exercise session, in person, on paper (handwritten solutions are fine).
  2. No later than at 23:59 next Monday, by email to dda-2014@helsinki.fi, as a PDF file that is easy to read on a computer screen (computer typeset solutions are recommended but not necessary).

You can combine the two approaches if you wish. You can answer in English or in Finnish (see the glossary). For programming exercises, put your code e.g. on Github and email a link.

The details of the grading procedure are as follows:

The deadlines are strict. Deadline extensions are given only in case of an illness or for similar reasons; a doctor's certificate will be required.

Social media

For informal discussion related to the course, you can join the following Facebook group:

Alternatively you can use the IRC channel #dda-2014 on IRCnet for real-time chat.

You do not need to follow these forums. All essential information will be provided on this web page. There is no guarantee that you will get assistance through these forums; please contact the lecturer or the teaching assistant if you need help.

Glossary

EnglishFinnish
graphverkko
node, vertexsolmu
edgekaari
degreeasteluku
regular graphsäännöllinen verkko
subgraphaliverkko
spanning subgraphvirittävä aliverkko
induced subgraphindusoitu aliverkko
walkkulku
pathpolku
cyclesykli
connected componentyhtenäinen komponentti
distanceetäisyys
radius-r neighbourhoodr-säteinen ympäristö
connected graphyhtenäinen verkko
diameterhalkaisija
girthympärysmitta
acyclicsyklitön
treepuu
forestmetsä
pseudotreepseudopuu
pseudoforestpseudometsä
independent setriippumaton joukko
vertex coversolmupeite
dominating setdominoiva joukko
matchingpariutus
edge coverkaaripeite
edge dominating setdominoiva kaarijoukko
maximal independent setmaksimaalinen riippumaton joukko
maximum independent setmaksimikokoinen riippumaton joukko,
suurin riippumaton joukko
minimal vertex coverminimaalinen solmupeite
minimum vertex coverminimikokoinen solmupeite,
pienin solmupeite
partitionositus
colouringväritys
domatic partitiondomaattinen ositus
edge colouringkaariväritys
edge domatic partitiondomaattinen kaariositus
bipartite graphkaksijakoinen verkko
factortekijä
factorisationtekijöinti
perfect matchingtäydellinen pariutus
directed graphsuunnattu verkko
undirected graphsuuntaamaton verkko
orientationsuunnistus
distributed algorithmhajautettu algoritmi
distributed computinghajautettu laskenta
distributed systemhajautettu järjestelmä
networkverkko
portportti
inputsyöte
outputtuloste
deterministic algorithmdeterministinen algoritmi
randomised algorithmsatunnaisalgoritmi
approximation algorithmapproksimointialgoritmi
approximation factorapproksimointisuhde
covering mappeitekuvaus
local neighbourhoodpaikallinen ympäristö
edge packingkaaripakkaus