Uni-Logo
Algorithms and Complexity
 

Distributed Algorithms
Block Seminar - Summer Term 2021
Fabian Kuhn

 


Introductory Meeting: Thursday, April 22, 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.

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.

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

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, 22nd of April (first week of the semester), 12:15 - 14:00: Introductory event.
  • By May 7: 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 June 8: (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.
  • Monday, July 19 : Presentations.

Paper List

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

No. Title Link Brief Description
1 Distance Computations in the Hybrid Network Model via Oracle Simulations Dagstuhl In the distributed HYBRID model, communication occurs via two modes. A local mode modeled by a graph, where only adjacent nodes can communicate and a global mode where any two nodes may communicate at limited bandwidth. This article gives improved results for various shortest paths problems. In particular, they leverage the fact that nodes that have more than average degree (= number of local neighbors) can take control of their neighbors to increase their own bandwidth via the global communication mode, thereby allowing them to learn large parts of the input graph and act as oracles for other nodes.
2 Improved Hardness of Approximation of Diameter in the CONGEST Model Dagstuhl It is known that computing the diameter of a graph in the distributed setting using small messages requires at least near-linear time. This paper shows that even finding something better than a 11/6-approximation requires polynomial time.
3 Improved Distributed Approximations for Maximum Independent Set ArXiv It is known that, in the distributed setting, finding a maximal independent set requires at least Omega(sqrt(log n / log log n)), even for randomized algorithms. A maximal independent set implies a Delta-approximation of the maximum independent set, where Delta is the maximum degree of the graph. This paper shows that finding an ((1+epsilon)Delta)-approximation of the maximum (even weighted) independent set can be done exponentially faster, in O(poly log log n) rounds, using small messages.
4 Distributed Dense Subgraph Detection and Low Outdegree Orientation ArXiv This paper shows that, in the distributed setting, dense subgraphs can be identified with a deterministic O(log n) time algorithm that uses large messages, or with a randomized O(log^3 n) time algorithm that uses small messages. Also, it is shown an efficient algorithm that orients edges such that every node has small outdegree.
5 Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs Dagstuhl It is known that, in the distributed setting, for all constant k, detecting if a graph contains a cycle of length exactly 2k requires at least Omega(sqrt(n)) for algorithms that use small messages. This paper, among other things, shows that 2k cycle detection, for k=3,4,5, can be solved in O(n^(1-1/k)).
6 Distributed Graph Problems through an Automata-theoretic Lens ArXiv This paper shows, among other things, that for a family of problems called LCLs, their distributed complexity is decidable efficiently if the network is an unlabeled path or cycle, meaning that we can take the description of the problem and automatically get what is the distributed time complexity of it, and an optimal algorithm for it.
7 Near Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ArXiv This article applies 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 (CONGEST, Broadcast Congested Clique, Streaming model). 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 in the same distributed models for the SSSP problem.
8 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. 1- Regarding the first problem, given a graph G with edge connectivity lambda, the goal is to identify at least one minimum cut, that is a collection of lambda edges whose removal disconnects the graph. To solve the problem, a graph sampling technique is employed that is usually used in the fault-tolerant network design context. 2- Regarding the second one, for a given unweighted n-vertex D-diameter graph G = (V, E) and integer lambda >= 1, a connectivity certificate is a subgraph H subset G satisfying that it is lambda-edge (or vertex) connected iff G is lambda-edge (or vertex) connected. The certificate is said to be sparse if H has O(lambda.n) edges.
9 Distributed Strong Diameter Network Decomposition ArXiv The authors answer an open problem and devise a randomised polylogarithmic time algorithm for constructing strong diameter network decompositions in the CONGEST model. Network decomposition is a powerful construct used to solve many different graph problems in the distributed setting. Although, similar results were previously known for the LOCAL model.
10 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. The paper in particular introduces an important randomized method to solve distributed graph problems.
11 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 omega(1) 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?
12 Distributed Approximation on Graph Powers ArXiv Consider the following setting: Given a graph G, you are asked to solve a problem on G^2. In graph theory, the kth power G^k is obtained from G by connecting any two nodes in G via an edge if their distance in G is at most k. The authors of this paper investigate two fundamental graph problems, namely minimum vertex cover and minimum dominating set, in the above setting, where they achieve new approximation and lower bound results in the distributed CONGEST model.
13 Distance-2 Coloring in the CONGEST Model ArXiv A distance-2 coloring of a graph is a coloring of the nodes such that nodes that are within distance 2 have different colors. While in the LOCAL model this problem can be easily reduced to the standard coloring problem, the situation is different if we restrict the message sizes. The authors give efficient deterministic and randomized distributed algorithms for this problem in the CONGEST model.
14 Single Source Shortest Paths in the CONGEST Model With Improved Bound ACM This work considers the Single Source Shortest Paths Problem (SSSP) in the CONGEST model. In this model we have a graph, where the nodes represent computational units that can communicate along edges with messages of small size. The goal is that each node learns its distance to some dedicated source node. It can be shown that this problem takes at least Omega(D+n^{1/2}) communication rounds, where n is the number of nodes and D is the diameter of the graph. This article gets very close to this lower bound by solving SSSP in O(D+n^{1/2}*D^{1/4})rounds.
15 Simple, Deterministic, Constant-Round Coloring in the Congested Clique ArXiv 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.
16 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.
17 Improved Deterministic Distributed Matching via Rounding ArXiv The author presents improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method.
18 Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover ArXiv This is one of the recent papers on graph algorithms in the massively parallel computation (MPC) model, an abstract model to study parallel computations by large clusters of computers. The paper in particular contains an elegant algorithm to find large matchings in a graph exponentially faster than in other (standard) distributed models.
19 An Efficient Distributed Algorithm for Constructing Small Dominating Sets Springer The paper is almost 20 years old. But it presents a very nice distributed solution to approximate the minimum dominating set problem. It shows very nicely how one can sometimes start from a sequential greedy algorithm and turn it into an efficient almost equally good distributed/parallel algorithm.
20 Latency, Capacity, and Distributed Minimum Spanning Tree ArXiv The paper studies the cost of distributed MST construction in the setting where each edge has a latency and a capacity, along with the weight. Edge latencies capture the delay on the links of the communication network, while capacity captures their throughput (in this case, the rate at which messages can be sent). The paper provides several tight bounds on the time and messages required to construct an MST, depending on how the edge latencies relate to the edge weights.
21 No Sublogarithmic-time Approximation Scheme for Bipartite Vertex Cover ArXiv Somewhat surprisingly, the authors of this paper show that computing a good enough approximate minimum vertex cover in the distributed setting can't be done in sublogarithmic time even on 2-coloured graphs of maximum degree 3 and even if we allow randomisation. Moreover, they show that this lower bound is actually tight on bounded degree bipartite graphs.
22 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.

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.