The field of distributed graph algorithms is a rapidly growing field in Theoretical Computer Science. The main goals in this field are to develop algorithms and methodologies that will support the correct and efficient operation of decentralized systems. The correctness, functionality, and efficiency of many decentralized systems rely on distributed algorithms over graphs. The classical example is the Internet. Newer applications include blockchains (e.g. Bitcoin), communication network between data-centers, autonomous vehicles, and modern cellular networks (e.g. 5G).

A distributed system is modeled as a communication graph, where the nodes of the graph are the processors connected to each other via communication links, and communication occurs in synchronous rounds. The goal is to develop fast algorithms for fundamental graph problems, where the input graph is the topology of the network. Efficiency is measured in terms of the number of communication rounds of the algorithm. This abstraction formalizes the empirical observation that, in many modern distributed systems, the main bottleneck is communication between nodes rather than local computation.

The field of distributed graph algorithms is rather active, keeps growing in popularity year by year (there are two main annual conferences and a few smaller conferences). This field builds on the classical field of graph algorithms while taking into account the constraints imposed in a distributed environment. Many new algorithms and algorithmic techniques have been developed recently. These recent results are promising candidates for becoming the foundational basis of this field.

The proposed meeting will bring together researchers in this dynamic field so that they can share their recent results and insights. We anticipate that new ideas and collaborations will result from a meeting dedicated to the topic of distributed graph algorithms. The potential participants of the meeting come from various countries and institutions, specifically from Israel, Japan, Europe and the USA. Following the Dagstuhl tradition of welcoming researchers in early stages of their career, we have included a few PhD students to the list of invitees. We hope the proposed meeting will strengthen the academic connection between this international research communities, especially between Japanese and non-Japanese researchers.

The participants come from various subfields within the field of distributed graph algorithms. The research interests of our invitees range from solving fundamental graph problems in the distributed setting, to modeling swarms of autonomous robots in 3D space. We believe a meeting with this diverse mix of researchers can have a very positive impact on the field, as ideas and techniques from one subfield can be applied to related subfield.

The main research topics that will be discussed in the meeting are:

Designing algorithms with an optimal running time has both theoretical and practical importance. Such a rare feat demonstrates a deep understanding of the computational character of a problem. Recently, there has been an increasing number of results in the field of distributed graph algorithms achieving optimal running times that meet the lower bounds. Nevertheless, some fundamental problems still exhibit a gap between their lower and upper bounds. The most famous such open problem is that of computing a Maximal Independent Set (MIS) in graphs. The MIS problem is a fundamental tool for symmetry breaking in distributed computing, and any improvement in this problem would immediately translate into an improved running time for a range of important distributed algorithms. MIS is only an example to one of many fundamental algorithmic problems (Set Cover, Spanning Tree, Dominating Set, Shortest Path computation, etc...) we wish to consider. The list of invitees includes the world's experts on this problems and on other fundamental problems.

Randomization is a fundamental tool in algorithm design. In fact, randomized algorithms for some problems are faster than the best known deterministic algorithms. This raises the open question of whether randomization is absolutely needed in order to achieve faster running times. Thus, the possibility of closing the gap in distributed computing between deterministic and randomized upper bounds for many problems is a long standing open problem. For example, the MIS problem admits a logarithmic time randomized algorithm, but no sublinear time deterministic algorithm is known. Understanding the power of randomization in the design of distributed algorithms is of fundamental importance. Any progress in this direction will have significant implications for the field.

Many techniques have been developed in the field of Algorithms. These techniques are useful in many models such as approximation algorithms of NP-hard problems, Online algorithms that make decisions without knowledge of the future, Streaming algorithms that read the input once and have limited memory, dynamic algorithms in which the input changes over time, and distributed algorithms that are characterized by a limited local view of the "world". Techniques such as Linear Programming, Primal-Dual algorithms, Randomization, Dynamic Programming, etc. have been proven to be useful in the development of algorithms for all of these settings. We plan to explore various algorithmic techniques that have been developed for non-distributed settings, and study their applicability in a distributed setting.

Each application has its particular characteristics that influence the applicability of distributed algorithmic solutions. Some examples of these special characteristics include: Coordination and synchronization of data centers is characterized by having huge traffic volumes over modest sized networks of tens or hundreds of nodes that are placed far away from each other. Vehicular communication networks, on the other hand, consist of vehicles that are close to each other and require relatively small amounts of communication. However, delay is a crucial factor in vehicular communication networks to obtain safety. Another example is Blockchain networks that consist of thousands of nodes with a dense communication pattern. Indeed, theoretical problems such as reaching consensus in a distributed fashion in the presence of faults turn out to be fundamental problems in the design of Blockchain systems. We plan to discuss how these specific requirements influence the design and applicability of distributed algorithms.