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:
  • Goldberg et al. (1988), Panconesi–Rizzi (2001): from k colours to ∆ + 1 colours in O(∆² + log* k) rounds.
• 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(m, n) are related to the special case of c = 2 and k = 2, i.e., 2-colourings of 2-subsets. In our notation, R(n, n) = R₂(n; 2). We do not need to consider Ramsey numbers R(m, n) 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.
  • Original paper: Ramsey (1930).
  • Our proof follows Nešetřil (Chapter 25 in Graham et al. 1995).

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:
  • Naor–Stockmeyer (1995): weak colouring in graphs with odd degrees.

Lecture 6: Exploration and rendezvous

• We will use results related to random walks to design deterministic algorithms for treasure hunt!
  • The cover time of a graph is the expected time until a random walk visits all nodes (worst case over all starting points).
  • The cover time of a graph is bounded by a polynomial in n; actually, it can be shown to be at most 2m(n−1), where m is the number of edges. We do not prove this result – for proofs, see, e.g., the textbooks by Motwani and Raghavan (1995), Sections 6.4–6.6, and Mitzenmacher and Upfal (2005), Section 7.4; the paper by Aleliunas et al. (1979); and courses on randomised algorithms.
• Aleliunas et al. (1979): existence of universal traversal sequences.
• Reingold (2008): construction of universal exploration sequences.
• Dessmark et al. (2006): deterministic rendezvous.
  • In trees, we use the fact that any tree is either centred or bicentred: there is either one unique central node, or there are exactly two central nodes that are joined by an edge.

Lecture 7: Local news

Course material

Solutions to exercises:

• How to prove that R₂(3; 2) = 6 and R₂(4; 2) = 18, by Janne Korhonen.

Schedule

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:

• The basic concepts of graph theory: graph, node (vertex), edge, degree of a node, directed and undirected graph, simple graph and multigraph, tree, connected graph, bipartite graph, regular graph, cycle graph, path graph, complete graph.
• Some classical graph problems: independent set, matching, graph colouring (vertex colouring), edge colouring, vertex cover.
• The difference between an independent set, a maximal independent set (not a subset of a larger independent set), and a maximum independent set (largest possible number of nodes). Similarly: matching, maximal matching, and maximum matching; vertex cover, minimal vertex cover, and minimum vertex cover.

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.