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.
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 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.
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 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. - 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 Ur-Rehman Mentor: Anisur Rahaman Molla
-
Randomized Broadcast in
Radio Networks with Collision Detection - Mohsen Ghaffari,
Bernhard Haeupler, Majid Khabbazian
Student: Rafael Gieschke Mentor: Chaodong Zheng
-
In-Network 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 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. -
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. - 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. - 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 -- 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)). -- -- -- --
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. -- --