Algorithms and Complexity

Distributed Algorithms
Seminar - Summer Term 2015
Fabian Kuhn


Seminar topic

All papers of the seminar deal with distributed algorithms that are carried out by multiple autonomous computing entities which are connected to each other through a network.

Administrative information

In order to get a grade, students have to study and later present the content of a specific paper from the field of distributed computing; see the list below. The seminar will be held as a block seminar on a day towards the end of the semester. In order to pass, attendance to all talks on the seminar day is mandatory. Your slides and talk should be in English. The presentation should last 45 minutes plus about 15 minutes of discussion.

We will meet the first time in the 3rd week of the semester, on Wednesday, May 6, at 12:15 in room 101-01-016.


The course is mainly directed towards Master students and 3rd year Bachelor students (and interested PhD students) of computer science or mathematics. There are no specific requirements, but students should be interested in mathematical and algorithmic questions and basic mathematical maturity is expected.

Written Report

You will have to write a report of at least half a page. The report should be a critical discussion of the paper. For exampe: Why is the paper interesting? Do you see any particular strengths or any weaknesses? Can the results be applied in practice or what would one need to change so that the results become practical? Do you see any interesting questions for follow-up research? Do you know any practical or theoretical work that is based on the paper?

In addition, every student who participates in the seminar will be assigned two papers which are presented by other students. You will need to prepare (and hand in before the seminar day) three questions for each of the two papers.


We require the following steps to ensure a high quality of the talks and hope that these will result in a good grade for you (all dates are still tentative and might change):

  • Until May 13: Decide for a paper.
  • Until June 5: Have a first meeting with your mentor (you need to read the assigned literature and have some idea on how to present it before this meeting).
  • At least 1 week before your talk: Discuss your (complete) slides with your mentor, so that he/she can give feedback.
  • One day before the presentation date: Hand in your report, an electronic copy of your slides, and the question on the two assigned papers.
  • Wednesday, July 8: Presentation

Papers (Tentative)

Your talk


Above we have a series of suggested papers which will be assigned on a first-come-first-serve basis. All presentations should cover the motivation for the problem as well as some technical parts of the paper in detail. Assume that the other participants know nothing about the subject. You are not supposed to present the whole paper, but just the aspects that were most intriguing to you. We encourage you to deviate from the logical structure of the paper and strive for the most lucid presentation of the topic. Furthermore you may want to have a look at how to design slides (e.g. link 1, link 2, link 3 (chapter 5)).


Below are the criteria according to which we judge a good presentation.

Motivated Talk

The speaker was motivated and kept the audience interested throughout the presentation.

Clearly Explained

The speaker made the material clear and comprehensible.

Knowledge Transfer

The (awake and participating) audience learned something.


The presentation was (too) difficult, easy, or just right to follow.

Prior Knowledge

The speaker did not assume inappropriate prior knowledge.


The presentation had a clear concept and discernible structure.

Encouraged Participation

The speaker actively encouraged participation and successfully led the discussion.