Algorithms and Complexity

Distributed Algorithms
Seminar - Summer Term 2016
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 30-35 minutes plus about 10 minutes of discussion.

We will meet the first time in the 2nd week of the semester, on Thursday, April 28, at 12:15 in room 106-00-007.


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.

More details will be published here soon.


We established the following rules to ensure a high quality of -- -- the talks and hope that these will result in a good grade for -- -- you:
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 12: Decide for a paper.
  • Until June 3: 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.
  • Monday, June 27: Presentation

Papers (Tentative)

  1. A Tight Space Bound for Consensus - Leqi Zhu
    Student: Simon Weidner    Mentor: Mohamad Ahmadi
    The paper proves that wait-free randomized binary consensus of n processes in shared-memory systems requires at least n-1 registers. The proof is based on a bivalency argument.
  2. Greedy sequential maximal independent set and matching are parallel on average - Guy E. Blelloch, Jeremy T. Fineman, Julian Shun
    Student: Jakob Stigler   Mentor: Hamid Ghodselahi
    A particularly simple algorithm to compute a maximal independent set (MIS) is the greedy sequential algorithm: each node has a unique ID. The MIS is then constructed in rounds. In each round, some node with smallest ID joins the MIS and this node with its children are removed. If the node IDs are chosen adverserially, this algorithm can take linear time. However, by contrast if the node IDs are chosen (uniformly) at random, this paper devises a parallel algorithm which mimics the above greedy sequential algorithm and takes polylogarthmic number of rounds with high probability.
  3. On the Complexity of Distributed Greedy Coloring - Cyril Gavoille, Ralf Klasing, Adrian Kosowski, and ALfredo Navarra
    Student: Zair Ur-Rehman   Mentor: Anisur Rahaman Molla
  4. Randomized Broadcast in Radio Networks with Collision Detection - Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
    Student: Rafael Gieschke   Mentor: Chaodong Zheng
  5. In-Network Analytics for Ubiquitous Sensing - Ittay Eyal , Idit Keidar , Stacy Patterson , Raphi Rom
    Student: Stefan Mörle   Mentor: Oleksii Saukh
  6. An Improved Distributed Algorithm for Maximal Independent Set - Mohsen Ghaffari
    Student: Pius Meinert   Mentor: Yannic Maus
    This paper presents a simple randomized algorithm to compute maximal independent set (MIS) in near-optimal time. They first (efficiently) studied the local complexity of the MIS problem, which is the time taken by each particular node to decide whether in MIS or not. Then by combining this result with some other techniques, it guarantees a global time complexity.
  7. Simple, Fast and Deterministic Gossip and Rumor Spreading - Bernhard Haeupler
    Student: Mostafa Mahmoud   Mentor: Chaodong Zheng
    This paper studies gossip algorithms for the rumor spreading problem, which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple, and robust solutions to the rumor spreading problem. In this article improves over the state of the art in several ways by presenting a deterministic gossip algorithm that solves the the k-local broadcast problem (send a message to all neighbors is distance k) in 2(k + log n) log n rounds.
  8. Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set - Mohsen Ghaffari
    Student: Philipp Jund   Mentor: Anisur Rahaman Molla
    This paper presents a near-optimal distributed approximation algorithm for the minimumweight connected dominating set (MCDS) problem. We use the standard distributed message passing model called the CONGEST model in which in each round each node can send O(log n) bits to each neighbor. The presented algorithm finds an O(log n) approximation in ~O (D + p n) rounds, where D is the network diameter and n is the number of nodes.
  9. Towards a complexity theory for local distributed computing - Pierre Fraigniaud, Amos Korman, and David Peleg
    Student: Janosch Deurer   Mentor: Yannic Maus

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. -- --