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 3035 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 10600007.
Requirements
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 followup 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.
Timeline
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)

A Tight Space Bound for Consensus  Leqi Zhu
Student: Simon Weidner Mentor: Mohamad Ahmadi
The paper proves that waitfree randomized binary consensus of n processes in sharedmemory systems requires at least n1 registers. The proof is based on a bivalency argument.  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.  On the
Complexity of Distributed Greedy Coloring  Cyril Gavoille,
Ralf Klasing, Adrian Kosowski, and ALfredo Navarra
Student: Zair UrRehman Mentor: Anisur Rahaman Molla

Randomized Broadcast in
Radio Networks with Collision Detection  Mohsen Ghaffari,
Bernhard Haeupler, Majid Khabbazian
Student: Rafael Gieschke Mentor: Chaodong Zheng

InNetwork Analytics for Ubiquitous Sensing  Ittay Eyal
, Idit Keidar
, Stacy Patterson
, Raphi Rom
Student: Stefan Mörle Mentor: Oleksii Saukh

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 nearoptimal 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. 
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 klocal broadcast problem (send a message to all neighbors is distance k) in 2(k + log n) log n rounds.  NearOptimal Distributed Approximation of
MinimumWeight Connected Dominating Set  Mohsen Ghaffari
Student: Philipp Jund Mentor: Anisur Rahaman Molla
This paper presents a nearoptimal 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.  Towards a
complexity theory for local distributed computing  Pierre
Fraigniaud, Amos Korman, and David Peleg
Student: Janosch Deurer Mentor: Yannic Maus
Your talk
Presentation
 Above we have a series of suggested papers which will be assigned on a  firstcomefirstserve 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)).    
Evaluation
 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. 
Difficulty
The presentation was (too) difficult, easy, or just right to follow. 
Prior Knowledge
The speaker did not assume inappropriate prior knowledge. 
Structure
The presentation had a clear concept and discernible structure. 
Encouraged Participation
The speaker actively encouraged participation and successfully led the discussion.  