Seminars

NO.162 Distributed Graph Algorithms

Shonan Village Center

November 4 - 7, 2019 (Check-in: November 3, 2019 )

Organizers

  • Guy Even
    • Tel Aviv University, Israel
  • Gregory Schwartzman
    • National Institute of Informatics, Japan

Overview

The field of distributed graph algorithms is a rapidly growing fi eld 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 fi eld builds on the classical fi eld 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 fi eld 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, speci fically 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 subfi elds within the fi eld 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 sub field can be applied to related sub field.

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

Bridging the gap between lower and upper bounds.

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 fi eld 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.

The power of randomization in distributed computing.

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 signifi cant implications for the field.

Harnessing algorithmic techniques for distributed algorithms.

Many techniques have been developed in the fi eld 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.

Fundamental algorithmic building blocks for applications.

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 specifi c requirements influence the design and applicability of distributed algorithms.