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.

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.

Timeline

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)

• (TAKEN) Solving the ANTS Problem with Asynchronous Finite State Machines - Yuval Emek, Tobias Langner, Jara Uitto and Roger Wattenhofer (Student: Marc Fuchs, Contact person: Anisur)
  In the Ants Nearby Treasure Search (ANTS) problem, n mobile agents, initially placed in a single cell of an infinite grid, collaboratively search for an adversarially hidden treasure. This paper study the ANTS problem considering some restrictions on the memory of the agents that they are controlled by an asynchronous (randomized) finite state machine. That is agents possess a constant-size memory and can locally communicate with each other through constant-size messages.
• (TAKEN) Fault-Tolerant ANTS - Tobias Langner, Jara Uitto, David Stolz, Roger Wattenhofer (Student: Bastian Meyer, Contact person: Anisur)
• (TAKEN) Construction and impromptu repair of an MST in a distributed network with o(m) communication - Valerie King, Shay Kutten, Mikkel Thorup (Student: Tobias Grugel, Contact person: Yannic)
  This paper study the communication cost i.e., total number of messages exchanged between nodes to compute a minimum spanning tree (MST) or spanning tree (ST) in an undirected graph. Previously it is known that computing MST or ST in a distributed congest network requires at least O(m) messages (where m is the number of edges in the graph), however, their protocols take o(m) messages. Further, they also study the message complexity to reconstruct MST or ST in dynamic networks with respect to edge insertion and deletion.
• What Can Be Computed Locally - Naor, Stockmeyer
  A problem can be solved locally if a node in a communication network can decide about its output on the basis of its c-hop view, where c is a constant independent from the size of the network. Two of the main results are:
  • There are non-trivial problems that can be solved locally.
  • There is a variant of the dining philosophers problem that can be solved locally.
• Network Decomposition and Locality in Distributed Computation - Awerbuch, Luby, Goldberg, Plotkin
  This paper introduces a method to efficiently partition the sets of nodes of a given graph into clusters with the following properties
  • Each cluster has low diameter
  • The clustergraph can be partitioned into few independent sets (there is no connection between two clusters which belong to the same independent set)
  Many (distributed) problems can be solved fast given a graph with small diameter; therefore they can be solved quickly on the clusters. The second property helps in dividing a big problem into small problems which then can be handled at the same time.
• Low diameter graph decompositions - Linial, Saks
  Linial and Saks improve the network decomposition of Awerbuch, Luby, Goldberg and Plotkin with the help of randomization. They also show that there are graphs which cannot be decomposed in a better way.
• Distributed Approximation Algorithms for Weighted Shortest Paths - Danupon Nanongkai
  The main result of this paper is a distributed (approximation) algorithm for computing single-source shortest paths (SSSP) in a weighted graph. The time complexity and the approximation ratio of the algorithm has improved over the previous results. They further extend the idea of SSSP algorithm to present an algorithm for all-pairs shortest paths (APSP).
• Simple parallel and distributed algorithms for spectral graph sparsification - Ioannis Koutis
  Graph sparsification is a powerful technique and being well studied problem in centralized settings. This paper presents the first distributed algorithm to compute spectral sparsification of a given graph i.e., a sparse graph which preserves the spectral properties of the original graph.
• Broadcasting in unreliable radio networks - Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa
  This paper considers broadcasting (an opration in which a single processor as a source sends a message to all other processors) in radio networks where the set of communication links includes two types of links. One type is reliable links which always deliver messages and induce a connected graph. The other one is unreliable links which sometimes fail to deliver messages and are changed from time to time.
• Near-Optimal Distributed Tree Embedding - Mohsen Ghaffari, Christoph Lenzen
  Embeddings of metrics into (a probability distributions over dominating) trees have many important applications due to the fact that many problems that appear difficult on general graphs often have nice and simple solutions on tree networks. This paper presents a distributed algorithm that constructs a probabilistic tree embedding in near-optimal number of rounds while expanding each pairwise distance by at most an expected logarithmic factor.
• Greedy sequential maximal independent set and matching are parallel on average - Guy E. Blelloch, Jeremy T. Fineman, Julian Shun
  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.
• Broadcast Throughput in Radio Networks: Routing vs. Network Coding - Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
  
• In-Network Analytics for Ubiquitous Sensing - Ittay Eyal , Idit Keidar , Stacy Patterson , Raphi Rom
  
• Distributed (\Delta+1)-Coloring in Linear (in Delta) Time - Barenboim, Leonid, Elkin, Michael Elkin and Kuhn, Fabian
  The distributed (\Delta + 1)-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. A (Delta+1) coloring of a given graph G=(V,E) is an assignment of one of Delta+1 colors to each of the nodes such that adjacent nodes do not have the same color. Sequentially, a (Delta+1) coloring can be computed easily (a simple greedy algorithm iterating through the nodes). In a long history of research this paper introduces an algorithm which can solve this problem in linear in Delta time (+ log*(n)).

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.