Uni-Logo
Algorithms and Complexity
 

Distributed Algorithms
Block Seminar - Summer Term 2020
Fabian Kuhn

 


Introductory Meeting: Thursday, May 14, 12:15-14:00

The introductory meeting for the seminar will take place as a video conference by using the video conferencing system zoom. The information on how to join the zoom meeting is available on following page:

Distributed Algorithms Seminar Zoom Information

Important note: This website can only be accessed from within the university network. This can be done either by accessing the internet via the university eduroam, or by establishing a VPN tunnel to the university network. Note that you have to cancel the VPN tunnel again before you enter the Zoom meeting.

The seminar will be held as a block seminar, all presentations will take place on one day (or on two half days) in the last three weeks of the semester (i.e., between July 13 and July 31). Once the list of students for the seminar is fixed, we will do a doodle poll to find the best possible day(s) for the presentations.

Topic

The main objective of the distributed algorithms seminar is to provide an opportunity to learn about some of the exciting topics current theoretical computer science research, specifically the field of distributed computing, has to offer.

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.

Assignment

In order to get a grade, students have to study and later present the content of a research paper. The slides and talk should be in English. The seminar will be held as a block seminar on one or two days towards the end of the semester. In order to pass, attendance to all talks on the seminar day is mandatory. After each presentation there will be a few minutes for questions and discussion.

To make the subsequent discussion broader and more interactive, each participant will be assigned two papers which are presented by other students. Even though you do not have to read those in-depth, you will have to prepare one or two question(s) for each of the two papers, the answer to which you might find interesting for yourself and/or the audience and ask your question after the respective talk.

Timeline

We require the following steps to ensure a good quality of the talks and hope that these will result in a good grade for you.

  • Thursday, 14th of May (first week of the semester), 12:15 - 14:00: Introductory event.
  • By May 25: Decide for a paper and notify us about your choice. Based on your choice you will be assigned a mentor soon after. Please send an email with your preference(s)
  • Until roughly mid of June: (the exact date will be specified later) Have a first meeting with your mentor (you need to read the assigned literature and have a rough idea how to present it or ask according questions).
  • Roughly three weeks before the talk: Send an email to your mentor in which you explain the structure of your presentation in sufficient detail so your mentor can provide feedback.
  • At least one week before your talk: Discuss your (complete) slides with your mentor, so that he/she can give feedback.
  • Not later than a day before the presentation date: Hand in an electronic copy of your slides, and questions on the two assigned papers.
  • July 31: Presentations.

Papers to be Presented on 31st of July

Paper List

The papers on the list will be assigned on a first-come-first-served basis.


No. Title Link Brief Description
1 Distributed exact weighted APSP in Near Linear Time ArXiv Computing even approximate all-pairs shortest paths in the main distributed model requires at least linear time in n. This paper gives the randomized algorithm that is optimal up to polylogarithmic factors. By this, the paper concludes a relatively long series of works on the problem.
2 Distributed edge Connectivity in Sublinear Time ArXiv The edge connectivity lambda is the minimum number of edges that must be removed so that the graph becomes disconnected. This work gives an algorithm that solves the problem exactly in O(n^{1-c}D^c + n^{1-c}) rounds (where c is a small constant) in the CONGEST model of distributed computing. The time complexity is therefore sublinear in n if D is. Previous algorithms achieve this only for very small edge connectivity or for approximations.
3 Near Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ArXiv They apply a surprisingly basic optimization technique (gradient descent) to compute (1+epsilon)-approximations for the so-called Transshipment problem in polylogarithmic number of rounds in various distributed models of computing. The much more basic single source shortest paths problem (SSSP) can be seen as a special case of the transshipment problem and this paper gives the best known algorithms for the same distributed models for SSSP.
4 Distributed Verification and Hardness of Distributed Approximation ArXiv In this paper, authors consider a model of distributed computing where messages must be small. In this model, authors show lower bounds on the distributed complexity of important graph problems, such as the computation of Minimum Spanning Tree.
5 Deterministic Distributed Vertex Coloring in Polylogarithmic Time ArXiv This paper studies the vertex coloring problem. More precisely, consider a graph G=(V,E) where V is the set of nodes (or vertices/processors) and E is the set of edges (communication links between nodes), and let Delta be the maximum degree in G. This paper shows how to color the nodes of a graph G with Delta^{1+o(1)} colors such that each neighboring nodes have different colors using poly(log n) rounds.
6 Small Cuts and Connectivity Certificates: A Fault Tolerant Approach Dagstuhl This paper studies connectivity problems in the CONGEST model, where each edge can carry at most O(log n) bits of information in each round of communication. The paper is focused on two problems; distributed computation of small edge cuts; and the computation of sparse connectivity certificates.
7 Simple, Deterministic, Constant-Round Coloring in the Congested Clique to appear This paper is the last in a series of papers that looks a the distributed coloring problem in the so-called congested clique model of distributed computation. It gives a relatively simple deterministic constant-time algorithm for the problem, improving on a much more complicated previous randomized algorithm.
8 The Locality of Distributed Symmetry Breaking ArXiv In this paper, authors show algorithms for different problems related to symmetry breaking, that is, MIS, ruling sets, coloring, and matching.
9 Improved Distributed Approximate Matching Link This paper studies the matching problem in the CONGEST model. Given a graph G, a matching of G is a subset of edges in G that are pairwise vertex-disjoint. The problem asks for a matching of maximum cardinality (or of maximum total edge weights in the weighted version of the problem). The paper improves the approximation ratio as well as running time of the distributed weighted and unweighted matching computation.
10 Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization ArXiv In this paper, authors show a polylogarithmic deterministic algorithm for network decomposition. Network decomposition is a fundamental building block used to solve many different graph problems in the distributed setting.
11 On Derandomizing Local Distributed Algorithms ArXiv This paper gives a simple generic derandomization technique. Together with a breakthrough from 2019, the paper implies that almost every distributed randomized algorithm can be made deterministic at only a polylogarithmic cost.
12 A lower bound for the distributed Lovasz Local Lemma ArXiv A lower bound for an important distributed graph problem (LLL) is presented. To achieve this goal, a lower bound for a simple problem, called Sinkless Orientation, is proved, using a technique called speedup simulation. Such technique has been later used, in other works, to prove lower bound for other problems as well. A simpler proof is provided by Chang et al.
13 An Automatic Speedup Theorem for Distributed Problems ArXiv In this paper, a technique to automatically prove lower bounds is presented. In particular, it is shown that, given a problem satisfying some criteria, it is possible to automatically define a problem that can be solved in exactly one round less than the original problem. The technique presented in this paper has been successfully used in following works to prove lower bounds in the LOCAL model of distributed computing.
14 Distributed Strong Diameter Network Decomposition ArXiv The authors answer an open problem and show that strong (O(log n),O(log n)) network decompositions can be computed in polylog n time with small messages. Given an n-vertex graph G= (V, E), a (X , D) network decomposition is a partition P of V into disjoint clusters of diameter at most D such that the graph obtained by contracting each of the clusters of P is properly X-colored. The decomposition P is said to be strong if each of the clusters has strong diameter at most D, i.e., if for every cluster C in P and every two vertices u, v in C, the distance between them in the induced graph G(C) of C is at most D. Although, similar results were previously known for the LOCAL model.
15 Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems ArXiv In the distributed setting there are important problems the solution of which can be verified by each node in parallel in O(1) rounds, even though in order to find such solution each node has to spend superconstant number of rounds. The usual complexity measure used to solve these problems is related to distance: how far must a node see in order to output its part of the solution? This paper considers a different complexity measure, that is volume: how many nodes must a node see in order to output its part of the solution?

Presentation

All presentations should cover the motivation for the problem, put it into a historic context (e.g., quickly stating the results of previous papers) 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. You should aim to give the audience knowledge about the key concepts and insights of the paper. We encourage you to deviate from the logical structure of the paper and strive for the most lucid presentation of the topic.

You may want to have a look at how to design slides (e.g. link 1, link 2, link 3). We further expect the presentation to motivate a lively discussion. Your presentation should not be a mere transfer of knowledge, but inspire an animated debate among the seminar participants.

We encourage discussion during and after a presentation as one of the main objectives of this seminar. The extent to which your own presentation instigates discussion as well as your own participation in the other presentations will influence your grade in this course.

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.