A theoretical running time analysis is a great tool for predicting the performance of algorithms, saving programmers from implementing and evaluating alternatives that are "obviously" worse. Though this works very well in many cases, there are situations where the predictions do not match practical observations. This often comes from the fact that practical problem instances have certain properties that make them well-behaved. In this talk, I present probabilistic network models that formalize these properties and discuss theoretical results based on these formalizations. In the course of this, I will discuss advantages and limitations of this model-based approach.

Thomas Bläsius studied computer science at the Karlsruhe Institute of Technology (KIT), where he continued to do his PhD in the field of Graph Drawing. Afterwards he spent five years as postdoc at the Hasso Plattner Institute (HPI) in Potsdam. Since then, his research focuses on the analysis of algorithms on realistic input models, with the aim to bridge the theory-practice gap between theoretical lower bounds and efficient practical algorithms. Since 2020, Thomas is junior professor and head of the Scalable Algorithms group at the KIT in Karlsruhe.

The dependability of distributed systems often critically depends on the underlying communication network, realized by a set of routers. To provide high availability, modern routers support local fast rerouting of flows: routers can be preconfigured with conditional failover rules which define to which port a packet arriving on this incoming port should be forwarded deterministically depending on the status of the incident links only. As routers need to react quickly, they do not have time to learn about remote failures.
My talk revolves around the fundamental question whether and how local fast rerouting mechanisms can be configured such that packets always reach their destination even in the presence of multiple failures, as long as the underlying network is still connected. I will show that this algorithmic problem is related to the field of disconnected cooperation, and offers a number of challenging research questions -- and sometimes surprising results. In particular, I will give an overview of state-of-the-art algorithmic techniques for different realistic graph classes (from dense datacenter topologies to sparse wide-area networks) and discuss lower bounds and impossibility results. While the main focus of the talk will be on deterministic algorithms, we will also take a glimpse at the power of randomization.

Stefan Schmid is a Professor at the Technical University of Berlin, working part-time for the Fraunhofer Institute for Secure Information Technology (SIT). MSc in Computer Science at ETH Zurich in Switzerland (minor: micro/macro economics, internship: CERN) and PhD in the Distributed Computing Group led by Prof. Roger Wattenhofer, also at ETH Zurich. Then postdoc at the Chair for Efficient Algorithms at the Technical University of Munich and at the Chair for Theory of Distributed Systems at the University of Paderborn, in Germany. From 2009 to 2015, he was a senior research scientist at the Telekom Innovation Laboratories (T-Labs) in Berlin, in 2013/14, an INP Visiting Professor at CNRS (LAAS), Toulouse, and in 2014, a Visiting Professor at Université catholique de Louvain (UCL). From 2015 to 2018, Associate Professor at Aalborg University, Denmark, and from 2018 to 2021 Professor at the University of Vienna, Austria. Since 2021, he serves as the Editor-in-Chief of the Bulletin of the European Association of Theoretical Computer Science (EATCS) and since 2019 as Editor of IEEE/ACM Transactions on Networking (ToN). He received the IEEE Communications Society ITC Early Career Award 2016 and an ERC Consolidator Grant 2019, and co-founded the startup company Stacktile supported by Germany's EXIST program.

Classes of sparse graphs --- such as classes with bounded expansion and nowhere dense classes --- enjoy strong structural and algorithmic properties. For example, FO-model checking is FPT on such classes. In this talk, we survey some locality properties of these classes, which might well open the way to new distributed algorithms in the LOCAL model.

Patrice Ossona de Mendez is researcher at the Centre d'Analyse et de Mathématique Sociales (CNRS/EHESS) at Paris, working part-time for the Computer Science Institute of Charles University (Prague, Czech Republic) and the Combinatorics center of Zhejiang Normal University (Jinhua, China). He received a PhD from EHESS in 1994, under the direction of Pierre Rosenstiehl and entered the CNRS in 1995. He received his habilitation from the Université Bordeaux I in 2009. Since 2009, he serves as the Editor-in-Chief of the European Journal of Combinatorics. His research interests are in Combinatorics, with focus on topological graph theory, structural properties of sparse combinatorial objects, limits of structures, and model theoretical aspects of structural graph theory.

Data centers are one of the most important settings in modern computer networking and distributed computing. Due to their importance they are very carefully architected, including the physical topology. While some distributed algorithms can be used "off the shelf" in data centers, the importance of performance and reliability, together with the carefully designed topologies, mean that it is often necessary to tailor our algorithms to the specifics of data center topologies. In this talk I will give an overview of data center topologies, with a focus on proposed next-generation "expander data centers" based on expander graphs. This will hopefully help the distributed algorithms community more easily contribute to the field of data center networking.

Michael is an Associate Professor in the Department of Computer Science at Johns Hopkins University, with a secondary appointment in the Department of Applied Mathematics and Statistics. He received his PhD from Carnegie Mellon University, and was a postdoctoral fellow at the Weizmann Institute of Science before joining JHU. His research is broadly in algorithms, with a focus on approximation algorithms, graph algorithms, distributed algorithms, and the theory of computer networking.

Structural graph parameters, such as degeneracy, treewidth and vertex cover number, offer various ways to measure the sparsity or simplicity of a graph. They are most widely studied in parameterised complexity, where the one asks which problem and parameter combinations admit fixed-parameter tractability – intuitively, which parameters behave in a way where a small value of the parameter makes a problem easy independent of the number of nodes in the graph.
In this talk, we review the hierarchy of structural parameters used in parameterised complexity, and discuss how these notions can be applied to distributed graph algorithms in LOCAL, CONGEST and CLIQUE models. While structural parameters have been implicitly used in distributed computing, we argue that wider exploration of structural parameters can offer new ways to think about real-world instances, and there is potential for "technology transfer" from parameterised complexity to distributed algorithmics.

Janne H. Korhonen is a postdoctoral researcher at IST Austria. He graduated from the University of Helsinki in 2014, and has been since jumping between various topics in distributed computing, machine learning, exact exponential algorithms and bioinformatics. His main current research interest is the theoretical limits of communication in distributed systems, in particular in CONGEST, congested clique and related models.

In this talk we will discuss one of the main techniques used to design distributed approximation algorithms for minor-closed families of graphs. We will focus on the maximum matching problem and its generalizations and use it to illustrate the main paradigm that encapsulates the principles behind this approach.

Andrzej Czygrinow works in the area of extremal graph theory and the theory of distributed algorithms. He has mainly worked on the so-called regularity method and its applications in graphs and hypergraphs. In addition, he is interested in using graph-theoretic tools to study distributed algorithms.

In the stochastic matching problem, we are given an arbitrary graph G, and the goal is to find a matching of an unknown random subgraph G' of G by querying only a small number of edges in G. In this talk, we show how with the machinery of distributed local algorithms, one can analyze a (non-distributed and global) Monte Carlo algorithm for the stochastic matching problem and prove that it obtains an almost maximum size matching with very few queries.
Based on joint works with MohammadTaghi Hajiaghayi and Mahsa Derakhshan (STOC'20, FOCS'20).

Soheil Behnezhad is currently a PhD candidate at the University of Maryland. He will join Northeastern University as an Assistant Professor in Fall 2022 and prior to that will spend a year at Stanford as a Motwani Postdoctoral Fellow. Soheil is broadly interested in theoretical computer science with a specific focus on the theoretical foundations of big data algorithms. His works revolve around massively parallel computation (à la MapReduce), streaming algorithms, graph sparsification, and dynamic algorithms, among others. During his PhD, Soheil has spent a year at the Simons Institute of UC Berkeley, a summer at TTI Chicago, and a summer at Google Research.

There are more and more distributed algorithms specially designed to work on specific graph classes, such as interval graphs or planar graphs. Before running such algorithms, one would like to be sure that the graph does belong to the class. In this talk, we tackle the problem of locally certifying graph classes. Specifically, we explain how we can design compact certification (i.e. proof-labeling schemes with logarithmic certificates) for planar, bounded genus, chordal, interval, circular-arc, and permutation graphs.

Pedro Montealegre is an Assistant Professor in the Engineering and Sciences Faculty at Universidad Adolfo Ibáñez in Santiago, Chile. He has an engineering degree with a major in mathematics from Universidad de Chile, later received his Ph.D. in Computer Science from the University of Orléans, and was a postdoctoral fellow at Universidad Adolfo Ibáñez. His research is mainly focused on distributed graph algorithms and the complexity of automata networks.