Open problems related to locality in distributed graph algorithms

Jukka Suomela · published on July 18, 2023 · last updated on July 1, 2024

[Jukka Suomela]

At ICALP 2023, I had a chat with Yi-Jun Chang, trying to convince him that not everything in the theory of distributed computing and locality is solved. I mentioned some of my favorite problems, and Yi-Jun rightly complained there isn’t a convenient web page where all of these are listed. So here it comes: a list of my favorite open problems related to the LOCAL model of distributed computing, as well as some closely-related models. Most of the questions are chosen so that solving them will likely require the development of new lower bound proof techniques. Now we just need someone to solve these…

LOCAL model

For definitions, see [L] [P]. As usual, \(n\) is the number of nodes, \(\Delta\) is the maximum degree of the graph, and for simplicity we will assume that both of these values are known. In what follows, I will often refer to locally checkable labeling problems or in brief LCLs; see [NS] for the definition of LCLs.

Vertex coloring. What is the complexity of vertex coloring, as a function of \(\Delta\)? This is known:

Here are some examples of concrete questions:

More generally, is there any reason to expect that \(O(\sqrt{\Delta})\) time or \(O(\Delta^2)\) colors is tight?

Fractional matching. What is the complexity of finding a maximal fractional matching, as a function of \(\Delta\)? This is known:

Here are some examples of concrete questions:

I conjecture that the answers to these questions are no, and the right tool for proving the lower bound seems to be round elimination.

Decidability of distributed complexity. Given an LCL problem \(\Pi\), is the round complexity of \(\Pi\) computationally decidable? That is, can we design an algorithm that takes a description of \(\Pi\) as input and outputs the asymptotic round complexity of \(\Pi\), with asymptotically tight upper and lower bounds? This is known:

Here are some examples of concrete questions:

Quantum-LOCAL model

For definitions, see [GKM] [AF].

Coloring cycles. Is there any quantum advantage for 3-coloring cycles? This is known:

Here are some examples of concrete questions:

Quantum advantage for LCLs. Is there any LCL problem that can be solved asymptotically faster in quantum LOCAL in comparison with classical randomized LOCAL? This is known:

Here are some examples of concrete questions:

I conjecture that quantum-LOCAL does not have any asymptotic advantage over randomized-LOCAL for LCL problems.

Non-signaling model

This refers to the model known as “\(\phi\)-LOCAL”, “physical locality”, “non-signaling model”, or “causal-LOCAL”. This is a model in which the only restriction is that the output of the system cannot violate causality; put otherwise, the system cannot violate the no-signaling from the future principle. Lower bounds for the non-signaling model imply lower bounds for quantum-LOCAL and classical LOCAL, as well as for finitely dependent processes. For definitions, see [GKM] [AF] [HL].

Coloring trees. Can we color trees with \(O(1)\) locality in the non-signaling model? This is known:

Here are some examples of concrete questions:

Note that a positive answer to the first question will imply a positive answer to the second question, but the converse is not necessarily true.

Non-signaling advantage for LCLs. Is there any LCL problem that can be solved asymptotically faster in the non-signaling model in comparison with quantum-LOCAL? Very little is known. Here are some examples of concrete questions:

VOLUME model

For definitions, see [RS].

Maximal matching. What is the complexity of finding a maximal matching, as a function of \(\Delta\)? This is known:

Here are some examples of concrete questions:

I conjecture that the right bound is \(2^{\Theta(\Delta)}\). See also the randomized algorithm in [NO] for some support for this conjecture.

LCL complexities. What are possible deterministic volume complexities of LCLs? This is known:

Here are some examples of concrete questions:

Dynamic-LOCAL and online-LOCAL models

For definitions, see [AELMSS].

Vertex coloring. How hard is vertex coloring in the dynamic-LOCAL and online-LOCAL models? This is known:

Here are some examples of concrete questions:

Promise-free separation for LCLs. Is it possible to separate LOCAL vs. dynamic-LOCAL vs. online-LOCAL for some LCL without a promise? This is known:

Here are some examples of concrete questions:

Acknowledgements

Many thanks to Yi-Jun Chang, Fabian Kuhn, Will Rosenbaum, and Yannic Maus for discussions, comments, and helpful suggestions!