ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The program consists of six invited talks, which are aimed at the general DISC audience.

The talks are designed to cover general aspects of a research topic rather than to present a particular new result. Such aspects include the advances achieved in the topic, the main remaining objectives, the technical obstacles, etc.

ADGA 2021 will be held on Monday, 4 October 2021, and will be co-located with DISC 2021. It will be possible to attend the workshop either as an online conference via Zoom or as a physical event at the University of Freiburg, Germany. For information about the registration, please go to the DISC 2021 registration page. The workshop will be chaired by Sebastian Brandt.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series.

Schedule

15:00 talk 1 Goran Zuzic: An Overview of Universal Optimality in Distributed Computing · video
15:35 talk 2 Laurent Feuilloley: Local Certification of Graph Classes · video
16:10 coffee break
16:30 talk 3 Peter Davies: LOCAL and Low-Space MPC: A Bridge Between Distributed and Parallel Computing · video
17:05 talk 4 Krzysztof Nowicki: Spanning Trees and Small Cuts in Congested Clique · video
17:40 coffee break
18:00 talk 5 Alkida Balliu: The Ubiquity of Δ-Coloring · video
18:35 talk 6 Anton Bernshteyn: Distributed Algorithms and Descriptive Combinatorics · video
19:15 Workshop ends

Invited Speakers

Alkida Balliu

University of Freiburg

Alkida Balliu is a postdoctoral researcher at the University of Freiburg, in the group of Fabian Kuhn. Prior to joining University of Freiburg, she was a postdoctoral researcher at Aalto University, in the group of Jukka Suomela. She received her PhD from Gran Sasso Science Institute, under the supervision of Pierre Fraigniaud. Her work focuses on understanding computability and hardness in the distributed computing area, with particular emphasis on the concept of locality.

The Ubiquity of Δ-Coloring

In the recent four years, there has been a fast progress in showing impossibility results for several fundamental problems in the LOCAL model of distributed computing. Our advances in understanding the automatic round elimination technique have played a big role in these achievements.

In this talk I will give an overview of the current state of the art of the automatic round elimination technique. We will see what are the tricks and methods that have worked so far, and what are some of the important open questions that we would like to comprehend. We will see that the study of the $\Delta$-vertex coloring problem under the round elimination framework had a direct effect in our understanding of several symmetry breaking problems.

Anton Bernshteyn

Georgia Institute of Technology

Anton Bernshteyn is an assistant professor in the School of Mathematics at the Georgia Institute of Technology. Anton received his Ph.D. from the University of Illinois at Urbana-Champaign in 2018 under the supervision of Alexandr Kostochka and Anush Tserunyan. Prior to his current position, Anton was a postdoc at Carnegie Mellon University. Anton’s primary research interests are combinatorics and descriptive set theory, with a particular emphasis on interactions between the two.

Distributed Algorithms and Descriptive Combinatorics

In this talk I will outline a recently discovered connection between distributed computing and an apparently very different subject, namely descriptive combinatorics. Descriptive combinatorics studies classical combinatorial problems—such as coloring, matching, etc.—on infinite structures (for example, infinite graphs) under additional topological or measure-theoretic regularity constraints. It turns out that distributed algorithms can provide powerful tools for working with such infinite structures; moreover, it is sometimes possible to establish exact translations of distributed results in the descriptive setting and vice versa. For example, efficient deterministic algorithms for locally checkable problems in the LOCAL model precisely correspond to continuous colorings. I will discuss this and several other instances of the interplay between distributed algorithms and descriptive combinatorics and mention a number of open problems.

Peter Davies

University of Surrey

Peter Davies is a lecturer (early-career fellow) at the University of Surrey, in the Distributed and Networked Systems group. His research interests are centred around distributed algorithms, and his background includes postdoctoral positions in distributed optimisation and learning with Dan Alistarh at IST Austria, and graph algorithms with Artur Czumaj at the University of Warwick. His PhD, also at the University of Warwick, was on communication algorithms for radio networks.

LOCAL and Low-Space MPC: A Bridge Between Distributed and Parallel Computing

In recent years, the fields of distributed and parallel graph algorithms, while always linked, have grown increasingly close. In particular, the emergent Massively Parallel Computation (MPC) model has been shown to have a strong connection to the classic LOCAL model of distributed computing. Under some restrictions, LOCAL algorithms can be run at an exponential speedup in MPC, via a process known as graph exponentiation. Furthermore, recent work has suggested that for many problems, this might be the best that one can hope to do in low-space MPC.

This talk will begin with an overview of what is known about this connection, both from an upper- and lower-bounds perspective. We will then discuss some recent results (joint work with Artur Czumaj and Merav Parter) showing that the power of low-space MPC is not limited to graph exponentiation, and demonstrate examples of algorithms which are super-exponentially faster than their LOCAL counterparts.

Laurent Feuilloley

University of Lyon 1

Laurent Feuilloley is a postdoctoral researcher, mainly interested in distributed and online algorithms, as well as graph theory. He got his PhD from University of Paris in 2018, was a postdoctoral fellow at Sorbonnes University and University of Chile, and is now a postdoc in University of Lyon 1.

Local Certification of Graph Classes

Many distributed graph algorithms have been designed for specific graph classes, such as regular or planar graphs. In some cases, e.g. regular graphs, the nodes of the network can check locally that the network indeed has the right structure, before running the algorithm. Unfortunately, in some cases, e.g. planar graphs, it is not possible to locally check the structure, and this can be problematic.

In this talk, I will review the recent results on the local certification of graph classes, which consists in certifying that the network belongs to a given class, using short labels on the nodes and a local verification algorithm.

[The talk will have a non-empty but small intersection with the gem talk I gave at PODC.]

Krzysztof Nowicki

BARC, University of Copenhagen

Krzysztof Nowicki is a postdoc at BARC, University of Copenhagen, in the group led by Mikkel Thorup. Krzysztof completed his PhD degree at University of Wrocław, under the supervision of Tomasz Jurdziński. His areas of interest focus on the algorithms for big data sets. Most of his past work concerns parallel algorithms for problems related to graph connectivity.

Spanning Trees and Small Cuts in Congested Clique

In the Congested Clique model, there are n players that perform computation in synchronous rounds. Each round consists of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange $O(\log n)$ bit messages. The main complexity measure is the number of rounds needed by the algorithm. The Congested Clique model may be considered as a special case of the Congest model in which the communication network is a clique, or as a special case of the Massively Parallel Computation model.

In this talk I will present a deterministic algorithm computing a maximal (in the sense of inclusion) spanning forest of a graph in a constant number of rounds, and briefly discuss its applications to the Minimum Spanning Tree problem, and the Edge Connectivity problem.

Goran Zuzic

ETH Zurich

Goran Zuzic is a postdoc at ETH Zurich, in the research group of Prof. Mohsen Ghaffari. He received his Ph.D. from the School of Computer Science at Carnegie Mellon University under the advisorship of Prof. Bernhard Haeupler. His thesis, titled Towards Universal Optimality in Distributed Optimization, won the 2021 ACM principles of distributed computing dissertation award. He has a broad interest in algorithms, with a focus on algorithms in the distributed setting and a fledging interest in applying tools from continuous optimization to overcome long-standing barriers for fundamental problems.

An Overview of Universal Optimality in Distributed Computing

Many distributed algorithms for optimization problems like the shortest path or the minimum spanning tree achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two long-standing fundamental questions in distributed computing:

(i) What network topology parameters determine the complexity of distributed optimization?

(ii) Are there universally-optimal algorithms that are as fast as possible on every topology?

A recent line of work on the so-called low-congestion shortcut framework answered both of these questions: (i) the network topology parameter is (up to polylogs) the low-congestion shortcut quality, and (ii) there indeed exist universally-optimal algorithms. In this talk, I will give an overview of the various pieces of the framework, explain how they interact to culminate in universally-optimal algorithms, as well as several other results of independent interest.