Seminar: Distributed Algorithms

Overview · Scope · Requirements · Grading · Report · Presentation · Repository · Schedule · Milestones · Feedback · Support · Tools · Start · Material · Voting · Topics



This seminar course focuses on the theoretical foundations of distributed computing, including the design and analysis of distributed algorithms, models of distributed computing, and computability and computational complexity from the perspective of distributed systems. For an introduction to the research area, see the lecture course on Deterministic Distributed Algorithms.

Prior knowledge of distributed systems is not necessary. However, students are expected to have (1) a basic knowledge of discrete mathematics, (2) interest in theoretical problems, theory of computation, algorithms, and computational complexity, and (3) some prior experience of scientific writing (e.g., writing a BSc thesis).

During the seminar course, each student will read original scientific publications, write a report (in English), and give a presentation (in English). The seminar is offered in autumn 2012, during the 1st and 2nd periods; we will meet on Thursdays at 2:15pm–4:00pm, in room C220. The course is worth 3 credits, and the course code is 58307301. The course instructor is Jukka Suomela.


We will interpret distributed computing broadly. The selection of possible topics of seminar reports will include papers that are of interest to a wider algorithmic audience, and students are also encouraged to suggest their own topics. Virtually any paper published in PODC or DISC will be on-topic in this seminar, as well as many papers from ICALP track C or SPAA.


The following parts are compulsory:

All deadlines are strict, and you will fail the course if you miss a deadline. Deadline extensions are given only in case of an illness or for similar reasons; a doctor's certificate will be required.

To play safe, try to finish your report early. It is perfectly fine to have your report finished already in September, in which case you do not need to do anything in October.


We will use the usual scale of 1–5.

The grading is based on all compulsory parts (quality of report, quality of presentation, quality of feedback), with most emphasis put on the report.

For a passing grade, you will have complete all compulsory parts in time, and your report and presentation must be of an acceptable level. In borderline cases, you will be given an opportunity to revise your report.

The highest grade should be achievable if you work hard, do your best, and listen to the feedback (both from the instructor and from other students).

This seminar course is worth 3 credits, which entails approximately 80 hours of work. The grading is calibrated so that roughly this amount of work suffices for a good grade. There is no need to overdo it. However, invest your working hours wisely — do not spend too much time reading papers, as you will also have to write something…

Seminar report

A seminar report is a short review paper: you explain some interesting results in your own words.

Content. A typical seminar report will consist of the following parts:

Superficially, your report should look like a typical scientific article. However, it will not contain any new scientific results, just a survey of previously published work.

In comparison with a typical BSc thesis written at our department, the main difference is that a BSc thesis is typically fairly long, broad, and shallow, while a seminar report is shorter, focuses on a small number of results, and goes deeper in the details.

If you compare your seminar report with the original publications on which it is based, the main differences are these:

Make sure that your seminar report (and presentation) shows that you have actually understood everything, it is completely clear to you, and now you are doing your best to explain the key ideas to others. Do not follow the structure of the original articles; come up with your own presentation that is much better than the original version! Ideally, pick ideas from several papers and synthesise.

Layout. Your seminar report should be:

Plagiarism. No kind of plagiarism will be tolerated, no matter how slight it is.

Everything that you write in your seminar report must be written in your own words. Use appropriate citations to make it clear which result comes from which publication.

All illustrations and examples should be your own original work. There is usually no need to use the same example as what was used in the original publications; by constructing your own examples you are also forcing yourself to actually understand the details of the result.

(If it is absolutely necessary to reuse illustrations or examples from other sources, make it very explicit in your report, with appropriate citations, and make sure you are not violating anyone else's copyrights. Remember that simply re-drawing a figure does not make it your own work.)


You will give a presentation on the topic of your seminar report. You can focus on some parts of your report.

Content. The presentation gives an informal overview of the topic of the seminar report.

Make sure that everyone in the audience gets a very good idea of the following:

  1. Precisely what was the problem that was studied? What was the model of computation? What are the assumptions?
  2. Precisely what is the result?

After that, you can try to explain why the result is true. For example, you might give a high-level overview of the algorithm, or illustrate it with some examples, or explain some interesting parts of the proof. All of this can be very informal — after all, there is very little time, and if someone is interested in the details, they can read your seminar report.

Slides. You will have to prepare presentation slides that support your presentation (for example, just using a whiteboard is not sufficient).

You can prepare your presentation in any format, as long as you can give the presentation using the IT equipment that is available in room C220. You can bring your own laptop, but make sure you have a plan B in case something goes wrong — it is your responsibility that your show starts on time.

Timing. The length of a presentation is 25 minutes, followed by 5 minutes for questions and discussion.

Timing is difficult, and timing is very important in presentations. Make sure that you rehearse your presentation, and double-check the timing. Ideally, prepare your presentation so that you can easily calibrate the timing on the fly.

Git repository

There is a shared Git repository for our seminar course.

Location. The repository is available at the CS department's computers, in the following directory:


At the CS department (e.g., on, the right command for cloning is:

git clone /home/group/dasem12/dasem12.git dasem12

On your own computer, first configure ssh so that ssh cs takes you to, using whichever authentication method you prefer. Then clone:

git clone ssh://cs/home/group/dasem12/dasem12.git dasem12

See the quick start guide to get started.

Uses. All students will keep up-to-date versions of their reports in the repository: both the full source code, as well as the compiled PDF version. There is no need to explicitly send around draft versions of your seminar report. Just make sure that everything is up-to-date in the Git repository, and the instructor and other students can find it there.

Feedback from one student to another is also provided through the Git repository, as plain text files.

Structure. In the repository, there is one subdirectory per student. If your name is John Doe, you will find your files in the subdirectory j.doe. This is your own area; you can add any files that you need there, you can edit everything that you find there.

In your own subdirectory, you are required to create the following files, in due time:

Use UTF-8 (or plain ASCII) as the encoding in the Latex source code and in the text files. All file names should be in plain ASCII; avoid strange characters and whitespace.

Once again, you will only edit your own subdirectory, while you are free to read everyone else's subdirectories.


The seminar meets in room C220 as follows:

6 Sep 2012 Introduction J. Suomela
13 Sep 2012 No meeting
20 Sep 2012 No meeting
27 Sep 2012 No meeting
4 Oct 2012 No meeting
11 Oct 2012 Guest lecture C. Lenzen Tri, tri again
Feedback session J. Suomela
1 Nov 2012 Guest lecture B. Keller,
J. Uitto
Spectral graph theory
Presentation T. Kuusisto A1
8 Nov 2012 Presentations J.-K. Kangas A2
M. Hilke B2
A. Hankalahti B4
15 Nov 2012 Presentations J. Hirvonen B5
J. Määttä C1
J. Rahkola D1
22 Nov 2012 Presentations M. Wahlroos D4
D. Consuegra D5
J. Väisänen Dangerous networks
29 Nov 2012 Presentations E. Peltonen D7
J. Mäki D8
6 Dec 2012 No meeting

The presentations (25 min each) are scheduled as follows:

2:15–2:40Presentation 1
2:50–3:15Presentation 2
3:25–3:50Presentation 3


The milestones for the seminar report are as follows:

6 Sep 2012Topic selected.
9 Sep 2012At least one edit.
16 Sep 2012At least 2 pages of text
(e.g., a rough outline in bullet points).
23 Sep 2012At least 4 pages of text.
30 Sep 2012At least 6 pages of text.
At least 1 illustration.
7 Oct 2012At least 8 pages of text.
14 Oct 2012At least 10 pages of text.
28 Oct 2012Readable and understandable version.
Most of the content in place.
11 Nov 2012Almost-final version ready for peer-review.
The total length should be approx. 10–15 pages,
and there should be plenty of illustrations.
25 Nov 2012Feedback from peer-review.
2 Dec 2012Revised version based on the feedback.
9 Dec 2012Final version ready for grading.

All deadlines are by 11:59pm, local time. Just make sure that you have pushed everything to our Git repository by the deadline.


You will receive feedback on your seminar report regularly throughout the course, and you will also receive feedback on your presentation after your talk.

Typically, the course instructor will provide at least some feedback each week — either common comments to all students or individual comments specifically on your work.

You will also receive brief feedback on your presentation from all students, and more detailed feedback on your report from three students. Just check everyone else's directories in the Git repository to find feedback on your work.

Giving feedback on reports. You will read the reports of those three students whose presentations are right after your presentation, wrapping around to the beginning. That is, if there are 15 presentations in total, and your presentation is 13th, you will read the reports related to the 14th, 15th, and 1st presentation. See the milestones for the deadlines.

You will find the reports that you are supposed to read in the Git repository, and you will write your feedback as plain text files in your own directory in the Git repository; see the structure of the repository for more details on the file naming conventions. Your feedback should contain the following parts:

  1. In your own words, describe the main idea of the report. This should be one or two paragraphs of text.
  2. Give some concrete, high-level ideas of how the report could be further improved to make it easier to follow, more enjoyable to read, more clear with the technical details, etc. This should be one or two paragraphs of text.
  3. List all mistakes that you spotted: misspellings, typographic details, etc. This list is as long as needed.

Please note that you are not expected to evaluate the report; there is no need to say if the report is good or bad. Just tell how it can be even further improved — there is always room for that.

Giving feedback on presentations. You will have to take part in at least 4 presentation sessions, and in those sessions, you will have to give feedback on all presentations (except your own presentation).

The deadline for giving feedback on presentations if the end of the week — if a presentation was on Thursday, you will have three days to write your feedback. Ideally, do it right after the presentations.

Your feedback should contain the following parts:

  1. In your own words, describe the main idea of the presentation. This should be one or two sentences of text. Note that the main idea of the presentation is not necessarily the same as the main idea of the report; a talk can have a different focus.
  2. Give some concrete ideas of how the presentation could have been improved. This should be two or three sentences of text.

Yes, the feedback is very brief, between three and five sentences of text. Again, you will not evaluate, just suggest improvements.

Online support

For real-time chat, join the IRC channel #dasem12 on IRCnet. You can use the IRC client "irssi" on

You can also email Jukka Suomela if you have any questions.


To pass this seminar course, you will have to use the following tools.

Latex. You will have to use Latex to typeset your seminar report. Make sure that you have read at least lshort and short-math-guide first. If you need help, check the FAQ or ask at TeX StackExchange.

If you do not have Latex, download TeX Live 2012 (for GNU/Linux) or MacTeX 2012 (for Mac OS X). On the CS department's computers, use, as it has an up-to-date version of Latex.

Always use the pdflatex command, never latex. I strongly recommend that you use latexmk or a similar tool to compile your report — direct interaction with Latex is a bit painful.

Git. We have a shared Git repository, for both version control and collaboration. If you are new to Git, our quick start guide helps you to get started. After that, there is plenty of documentation available.

Drawing tools. You will need a vector graphics editor for drawing illustrations. It is absolutely necessary that you can export drawings in the PDF format for inclusion in your seminar report. For GNU/Linux, you can try, e.g., Inkscape or Ipe. For OS X, OmniGraffle might be a good option.

Presentation tools. You will also need a tool for preparing your presentation slides. Latex experts may want to use Beamer; for the rest of us, LibreOffice Impress, Microsoft PowerPoint, or Apple Keynote will do.

Quick start

Open an ssh connection to

Preparations. You will do this only once.

cd ~
git clone /home/group/dasem12/dasem12.git dasem12

Now you will have a directory ~/dasem12 in your home directory.

Editing. If your name is John Doe:

cd ~/dasem12/j.doe

Now with your favourite text editor, edit the file report.tex. Compile everything by running:


Open the document report.pdf and make sure that it looks good. Commit your changes:

git add -A
git commit -m 'Explanation of my edits.'

Collaboration. First pull everyone else's changes:

git pull

And then push your own changes:

git push

Next steps. Learn how to use the following commands:

git status
git diff

Background material

For introductory material related to the field of distributed computing, see the following resources:

Selecting your topic

The deadline for selecting your topic is 6 September 2012.

Own topic. If you have your own suggestion of a topic, please email the course instructor before the first meeting.

From the list. If you prefer the suggested topics, proceed as follows:

As there are 19 topics, the file topics.txt has to contain 19 lines of text. All lines have to be distinct. Each line consists of a two-character code (for example, "A1") followed by the newline character (ASCII code 10). Therefore the total size of the file should be precisely 19 × 3 = 57 bytes.

The file has to be in the Git repository on 6 September 2012. The topics will be assigned on 7 September 2012.

The topics will be assigned as follows:

Suggested topics

The articles listed after each topic are merely examples of possible starting points for further reading. Please remember that you can also suggest your own topic!

A. Global problems

A1. Shortest paths

A2. Spanning trees

B. Local problems

B1. Colour reduction

B2. Maximal matchings

B3. Maximal independent sets

B4. Fast graph colouring

B5. Recent breakthroughs

B6. Strictly local algorithms

C. Lower bounds

C1. Lower bounds for graph colouring

C2. Lower bounds for approximations

C3. Lower bounds for linear programs

D. Models of computing

D1. Beeping

D2. Computing with advice

D3. Verification

D4. Robots in the plane

D5. Robots in a graph

D6. Routing

D7. Wireless communication

D8. Consensus