# Deterministic Distributed Algorithms

## Summary

The intensive course on Deterministic Distributed Algorithms is offered 10–21 May 2010. The course meets daily from 12pm to 2pm. The course instructor is Jukka Suomela.

This is an advanced (Master level) course, so it is expected that the participants have a BSc degree (or equivalent). No specific courses are required – interest in algorithmic problems and a basic knowledge of discrete mathematics is sufficient (see below for more details).

The course is not based on any textbook. Presentation slides will be posted on this page, as well as pointers to additional material. All course material will be in English. Lectures are given in English, if there are foreigners present. The participants can write their report in Finnish or in English.

The volume of the course is 3 cr. There is no exam, and the grading is pass/fail. To pass the course, you are required to:

1. take part in the lectures and exercise sessions (at least 6 times out of 9)
2. write up your answers to all exercises, and return your report no later than at 6pm on Friday, 21 May 2010; the deadline is strict.

You can email the course instructor if you have any questions. If you use IRC, you can try to join the channel #dda-2010 on IRCnet (instructions).

## Course content

The course covers selected topics in distributed computing; the focus is on deterministic distributed algorithms. The model of computation is the same as the one studied in the seminar course in autumn 2009; however, there is only a little overlap between the topics of the seminar and the topics of this course.

Lecture 1: Introduction

• Exactly what does it mean if we “solve problem P in time T by using a deterministic distributed algorithm”? Key terms: local input, communication round, local output.
• First model: the port-numbering model.
• Techniques for proving negative results in the port-numbering model: covering graphs and covering maps in port-numbered graphs.
• An example of a simple distributed algorithm in the port-numbering model. Key technique: using bipartite double covers.
• Remark: covering graphs are a graph-theoretic concept, usually studied in the context of ordinary graphs (without a port numbering, and without any references to distributed computing). We adapt the definitions so that they apply to port-numbered graphs, following Angluin (1980).

Lecture 2: Graph colouring and other algorithms with a log-star running time

• Definitions: iterated logarithm (log-star, log*), directed pseudoforest.
• Second model: networks with unique identifiers.
• Unique identifiers form a colouring; it is sufficient to focus on colour reduction algorithms that decrease the number of colours.
• Colour reduction in directed pseudoforests:
• Cole–Vishkin (1986): from k colours to O(log k) colours in one round.
• Linear-time algorithm: from k colours to k − 1 colours in one iteration.
• Combination: from k colours to 3 colours in O(log* k) rounds.
• Colour reduction in bounded-degree graphs:
• Applications?

Lecture 3: Basics of Ramsey theory

• Ramsey's theorem and Ramsey numbers.
• More specifically: Ramsey's theorem for hypergraphs and generalised Ramsey numbers.
• Key concept: monochromatic subsets.
• Our notation follows Radziszowski (2009). Note that the “classical” Ramsey numbers R(mn) are related to the special case of c = 2 and k = 2, i.e., 2-colourings of 2-subsets. In our notation, R(nn) = R2(n; 2). We do not need to consider Ramsey numbers R(mn) for m ≠ n.
• Interpretations of Ramsey's theorem:
• 1-subsets: pigeonhole principle.
• 2-subsets, 2 colours: cliques or independent sets in graphs.
• 2-subsets: monochromatic cliques in edge-coloured complete graphs.
• k-subsets: monochromatic cliques in edge-coloured complete hypergraphs.
• Proof of Ramsey's theorem.

Lecture 4: Applications of Ramsey theory: lower-bound results and more

• Background and some earlier results: Linial (1992), Naor–Stockmeyer (1995)
• We use Ramsey's theorem to show that constant-time algorithms cannot find large independent sets in cycles.
• One application of Ramsey's theorem: we can choose identifiers so that there is a long chain of nodes that produce identical outputs. Shows that symmetry-breaking fails somewhere.
• Repeated applications of Ramsey's theorem: several chains. Shows that symmetry-breaking fails almost everywhere.
• Original paper: Czygrinow et al. (2008).
• Corollaries: graph colouring, maximal independent sets, vertex covers, ...

Lecture 5: Weak colouring and other algorithms with constant running time

• Another model – port numbering and orientation:
• Strictly weaker than unique identifiers.
• Strictly stronger than port numbering.
• Weak colouring: labelling of nodes such that each non-isolated node has at least one neighbour with a different label.
• In some cases, symmetry can be broken in constant time by using both port numbering and orientation:

Lecture 6: Exploration and rendezvous

Lecture 7: Local news

## Course material

 Lecture 0 (alternative version) last updated on 2010-05-19 Lecture 1 (alternative version) last updated on 2010-05-19 Lecture 2 (alternative version) last updated on 2010-05-19 Lecture 3 (alternative version) last updated on 2010-05-19 Lecture 4 (alternative version) last updated on 2010-05-19 Lecture 5 (alternative version) last updated on 2010-05-19 Lecture 6 (alternative version) last updated on 2010-05-19 Lecture 7 (alternative version) last updated on 2010-05-19 Exercises last updated on 2010-05-17

Solutions to exercises:

## Schedule

 Monday 10 May: lecture 1 room B222 Tuesday 11 May: lecture 2 room B222 Wednesday 12 May: lecture 3 room B222 Thursday 13 May: holiday Friday 14 May: exercise session I room B222 Monday 17 May: lecture 4 room B222 Tuesday 18 May: lecture 5 room B222 Wednesday 19 May: lecture 6 room D122 Thursday 20 May: exercise session II room B222 Friday 21 May: lecture 7 room B222 return your report by 6pm

The lectures and exercise sessions are held in the Exactum building, from 12:15 to 14:00. The course schedule is available for download in iCalendar format.

## Before the first lecture

It is recommended that the participants review the definitions of the following terms before the first lecture:

## Exercises

There are 5 exercises, and they are related to the topics covered in lectures 1–5. The exercises are announced on this web page beforehand.

The exercise sessions are reserved for discussing exercises, presenting solution ideas, and asking for advice. Session I focuses on exercises 1–3 and session II focuses on exercises 3–5. You should have made a serious attempt to solve the exercises before the exercise session, but you do not need to have solutions to all exercises available by then.

In your final report you must have a solution to all exercises (except those that are marked "optional"). You are welcome to ask questions and learn from other participants during the exercise sessions. You can also use any other sources, such as textbooks and original scientific articles. However, your final report must be self-contained (with full proofs of all claims that you make), you must disclose all sources that you used (by using appropriate citations, just like in any scientific writing), and naturally everything must be written by yourself, in your own words.

Your report should be easy to read. You should prepare it by using an appropriate typesetting software such as Latex – hand-written reports are not accepted. Email your report to the course instructor as a PDF file. No specific style is required – for example, you can use “article” or “amsart” style in Latex. You do not need to write an introduction or anything else besides your answers to the exercises; you can assume that the reader has taken the same course.

Please note that many of the exercises are open-ended: there is no single correct answer. You do not need to give the best known answer; it is sufficient to give a slightly weaker answer that is reasonably easy to prove.