# 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:

- week 1 · updated on 2014-03-11
- week 2 · updated on 2014-03-20
- week 3 · updated on 2014-03-27
- week 4 · updated on 2014-04-03
- week 5 · updated on 2014-04-10
- week 6 · updated on 2014-04-24

# Schedule

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

Lectures are given on

- Tuesdays from 12:15 to 14:00 in room B222, and
- Thursdays from 12:15 to 14:00 in room B222.

The exercise group meets on

- Fridays from 12:15 to 14:00 in room B119.

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.

# Grading

There are two grading options.

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

The options are available as follows:

- Course exam: option 1 and option 2.
- First separate exam (renewal exam): option 1 and option 2.
- Other separate exams: option 2 only.

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:

*e* = exercise points, scale 0–12, as a whole integer, rounded up
*p*_{i} = grading of problem *i* in the exam, scale 0–12 (*i* = 1, 2, …, 5)
*S* = *p*_{1} + *p*_{2} + … + *p*_{5}
*S*_{i} = *e* + *S* − *p*_{i}
*T* = max {*S*, *S*_{1}, *S*_{2}, …, *S*_{5}}

# 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:

- No later than
**at 13:59 on the same Friday**, during the exercise session, in person, on paper (handwritten solutions are fine).
- 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:

- You will get 0.5 points for each solution that is readable, understandable, mostly correct, and returned on time according to one of the above procedures. For all other solutions you will get 0.0 points.
- If you choose to return more than 4 solutions, all of them will be graded. However, each week you can get at most 2.0 points in total.

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.

# Glossary

English | Finnish |

*graph* | verkko |

*node, vertex* | solmu |

*edge* | kaari |

*degree* | asteluku |

*regular graph* | säännöllinen verkko |

*subgraph* | aliverkko |

*spanning subgraph* | virittävä aliverkko |

*induced subgraph* | indusoitu aliverkko |

*walk* | kulku |

*path* | polku |

*cycle* | sykli |

*connected component* | yhtenäinen komponentti |

*distance* | etäisyys |

*radius-**r* neighbourhood | *r*-säteinen ympäristö |

*connected graph* | yhtenäinen verkko |

*diameter* | halkaisija |

*girth* | ympärysmitta |

*acyclic* | syklitön |

*tree* | puu |

*forest* | metsä |

*pseudotree* | pseudopuu |

*pseudoforest* | pseudometsä |

*independent set* | riippumaton joukko |

*vertex cover* | solmupeite |

*dominating set* | dominoiva joukko |

*matching* | pariutus |

*edge cover* | kaaripeite |

*edge dominating set* | dominoiva kaarijoukko |

*maximal independent set* | maksimaalinen riippumaton joukko |

*maximum independent set* | maksimikokoinen riippumaton joukko, suurin riippumaton joukko |

*minimal vertex cover* | minimaalinen solmupeite |

*minimum vertex cover* | minimikokoinen solmupeite, pienin solmupeite |

*partition* | ositus |

*colouring* | väritys |

*domatic partition* | domaattinen ositus |

*edge colouring* | kaariväritys |

*edge domatic partition* | domaattinen kaariositus |

*bipartite graph* | kaksijakoinen verkko |

*factor* | tekijä |

*factorisation* | tekijöinti |

*perfect matching* | täydellinen pariutus |

*directed graph* | suunnattu verkko |

*undirected graph* | suuntaamaton verkko |

*orientation* | suunnistus |

*distributed algorithm* | hajautettu algoritmi |

*distributed computing* | hajautettu laskenta |

*distributed system* | hajautettu järjestelmä |

*network* | verkko |

*port* | portti |

*input* | syöte |

*output* | tuloste |

*deterministic algorithm* | deterministinen algoritmi |

*randomised algorithm* | satunnaisalgoritmi |

*approximation algorithm* | approksimointialgoritmi |

*approximation factor* | approksimointisuhde |

*covering map* | peitekuvaus |

*local neighbourhood* | paikallinen ympäristö |

*edge packing* | kaaripakkaus |

## Social media

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

Alternatively you can use the IRC channel

#dda-2014on 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.