Dagstuhl Seminar 24471
Graph Algorithms: Distributed Meets Dynamic
( Nov 17 – Nov 22, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24471
Organizers
- Keren Censor-Hillel (Technion - Haifa, IL)
- Yasamin Nazari (VU Amsterdam, NL)
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK)
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US)
Contact
- Michael Gerke (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
This seminar brought together researchers from two research communities on distributed and dynamic graph algorithms. In dynamic settings, algorithms receive updates to the graph, and should update the solution efficiently. In many distributed settings, computation takes place in a decentralized manner over a network or multiple machines. The input is distributed among multiple computing devices that need to communicate to find a solution to a given problem. The first connection between these models that was explored in the seminar is the technical toolbox. In recent years, there has been a growing number of results in both areas that use similar algorithmic tools and technical ideas. Examples of these common technical tools include expander-based techniques, truncating Vizing chains for improved edge colouring, algebraic techniques based on matrix multiplication, spanners and hopsets, clustering coresets, etc.
While some of these techniques have found applications in one or both of these models, there are often technical challenges in applying them in different settings and knowledge of models of specific tools is needed. This is why the seminar aimed to increase collaborations and discussions between the two communities. The second type of connection is from a modeling point of view, motivated by practice. In many practical big data settings the input is both distributed and dynamic at the same time. First, it is stored in a decentralized way over many machines, and second, the input changes over time. Few talks focused on the models that combine multiple computational settings.
The format of the seminar was as follows: the first day included an introduction session in addition to an ice-breaker „research speed-dating“ event. In this ice-breaker event, participants were paired together in several short sessions with an attempt to pair participants who are not already familiar with each other's work. We had 4 plenary overview/survey talks, and the rest of the presentations were 20 minute talks and 10 minutes of questions and discussions. We also had two engaging open problem sessions in addition to various allocated times for collaboration.
We aimed to invite a diverse group of participants, both based on demographic factors and geographic affiliation, as well as seniority level. We had participants from Europe, North America, and Asia, and with experiences ranging from PhD students and postdocs to academic and industry research with varied level of seniority.
Creative Commons BY 4.0
Thatchaphol Saranurak, Keren Censor-Hillel, Yasamin Nazari, and Eva Rotenberg
In modern computational systems, the need to handle large-scale inputs imposes interesting computational challenges. Two such challenges are (1) the need to distribute the computation over multiple units, and (2) the dynamic nature of the input, which may undergo changes over time. A particular class of problems studied in these settings is when the input to the computational task is a huge graph.
The field of dynamic graph algorithms addresses efficiently processing edge/vertex insertions/deletions in the input graph. In distributed graph algorithms, the input resides across multiple machines, and the goal is to solve the problem while minimizing the number of rounds of communication. Both of these rich research areas have been extensively studied since at least the 1980’s. We know of efficient algorithms for a large variety of tasks, such as shortest paths problems, coloring, subgraph finding, symmetry breaking, approximations, and many more. However, there are still fundamental problems with no known efficient solutions in some of these models, and even more where the exact complexity of computation is yet to be determined. In the recent years, a number of influential works show how transferring ideas from one of these models to the other provides progress on some of the long-lasting open problems.
The goal of this Dagstuhl Seminar is to build a bridge between the two research communities of dynamic graph algorithms and distributed computing, by working together on joint research frontiers. The aim is to provide a pivotal ground for future growth of these thriving areas:
- Transfer of knowledge between the dynamic and distributed settings both on the algorithms (upper bound) and complexity (lower bound) side. Some problems in which this shared knowledge has shown potential are: shortest paths, matching, maximal independent set, coloring, clustering, and flows. For some of these areas there are already common toolkits being utilized such expander decomposition, low diameter network decomposition, algebraic tools, distance and cut sparsification, and sketching tools. This common toolkit suggests a concrete way forward for transferring ideas. We will explore tools and ideas for improved algorithms, and we will exchange knowledge about techniques for proving lower bounds, which are an essential component of understanding the computational abilities of any model of computation.
- Advancing the landscape of fast algorithms for the combined distributed dynamic setting. This setting is very natural, and very well-motivated by practice. While there has been some recent work in this direction, there is still very little known on this overlapping setting. New solutions in such a model may even improve the state-of-the-art for some problem in more than one model; for instance, an adaptive dynamic distributed algorithm may be useful as a subroutine for a static distributed algorithm.
Keren Censor-Hillel, Yasamin Nazari, Eva Rotenberg, and Thatchaphol Saranurak
Please log in to DOOR to see more details.
- Sepehr Assadi (University of Waterloo, CA) [dblp]
- Alkida Balliu (Gran Sasso Science Institute - L'Aquila, IT) [dblp]
- Aaron Bernstein (New York University, US) [dblp]
- Sayan Bhattacharya (University of Warwick - Coventry, GB) [dblp]
- Joakim Blikstad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Sebastian Brandt (CISPA - Saarbrücken, DE) [dblp]
- Karl Bringmann (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Keren Censor-Hillel (Technion - Haifa, IL) [dblp]
- Yi-Jun Chang (National University of Singapore, SG) [dblp]
- Shiri Chechik (Tel Aviv University, IL) [dblp]
- Keerti Choudhary (Indian Institute of Technology - New Delhi, IN) [dblp]
- Martin Costa (University of Warwick - Coventry, GB) [dblp]
- Tijn de Vos (Paris Lodron Universität Salzburg, AT) [dblp]
- Michal Dory (University of Haifa, IL) [dblp]
- Aditi Dudeja (Paris Lodron Universität Salzburg, AT) [dblp]
- Faith Ellen (University of Toronto, CA) [dblp]
- George Giakkoupis (INRIA - Rennes, FR) [dblp]
- Seth Gilbert (National University of Singapore, SG) [dblp]
- Christoph Grunau (ETH Zürich, CH) [dblp]
- Magnús M. Halldórsson (Reykjavik University, IS) [dblp]
- Adam Karczmarz (University of Warsaw, PL & IDEAS NCBR, Warsaw, PL) [dblp]
- Fabian Daniel Kuhn (Universität Freiburg, DE) [dblp]
- Jakub Lacki (Google - New York, US) [dblp]
- Quanquan C. Liu (Yale University - New Haven, US) [dblp]
- Yannic Maus (TU Graz, AT) [dblp]
- Danupon Nanongkai (MPI für Informatik - Saarbrücken, DE) [dblp]
- Yasamin Nazari (VU Amsterdam, NL) [dblp]
- Alexandre Nolin (CISPA - Saarbrücken, DE)
- Krzysztof Nowicki (Wroclaw, PL) [dblp]
- Dennis Olivetti (Gran Sasso Science Institute - L'Aquila, IT) [dblp]
- Ami Paz (CNRS - Gif-sur-Yvette, FR) [dblp]
- Richard Peng (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Vijaya Ramachandran (University of Texas - Austin, US) [dblp]
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK) [dblp]
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US) [dblp]
- Shay Solomon (Tel Aviv University, IL) [dblp]
- Jukka Suomela (Aalto University, FI) [dblp]
- Jan van den Brand (Georgia Institute of Technology - Atlanta, US) [dblp]
- Virginia Vassilevska Williams (MIT - Cambridge, US) [dblp]
- David Wajc (Technion - Haifa, IL) [dblp]
- Tianyi Zhang (ETH Zürich, CH) [dblp]
- Anna Zych-Pawlewicz (University of Warsaw, PL) [dblp]
Classification
- Data Structures and Algorithms
- Discrete Mathematics
- Distributed / Parallel / and Cluster Computing
Keywords
- Algorithms design and analysis
- dynamic graphs
- distributed graph algorithms
- algorithmic complexity
