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:

• We can find a \((\Delta+1)\)-coloring in \(O(\sqrt{\Delta \log \Delta} + \log^* n)\) rounds [MT] [BEG] [FHK] [B]
• We can find an \(O(\Delta)\)-coloring in \(O(\sqrt{\Delta} + \log^* n)\) rounds [BEG]
• We can find an \(O(\Delta^2)\)-coloring in \(O(\log^* n)\) rounds [L]
• We cannot find a \(g(\Delta)\)-coloring in \(f(\Delta) + o(\log^* n)\) rounds for any \(f\) and \(g\) [L]
• We cannot find a \(\Delta\)-coloring in \(f(\Delta) + O(\log^* n)\) rounds for any \(f\) [BFHKLRSU]

Here are some examples of concrete questions:

• Can we find a \((\Delta+1)\)-coloring in \(O(\Delta^{0.499} + \log^* n)\) rounds?
• Can we find a \((\Delta+1)\)-coloring in \(O(\log \Delta + \log^* n)\) rounds?
• Can we find a \((\Delta+1)\)-coloring in \(O(\log^* n)\) rounds?
• Can we find an \(O(\Delta)\)-coloring in \(O(\log^* n)\) rounds?
• Can we find an \(O(\Delta^{1.001})\)-coloring in \(O(\log^* n)\) rounds?
• Can we find an \(O(\Delta^{1.999})\)-coloring in \(O(\log^* n)\) rounds?

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:

• We can find a maximal matching in \(O(\Delta + \log^* n)\) rounds [PR]
• We can find a maximal matching in \(O(\Delta)\) rounds in bipartite graphs [HKP]
• We can find a maximal fractional matching in \(O(\Delta)\) rounds [ÅS]
• We cannot find a maximal matching in \(f(\Delta) + o(\log^* n)\) rounds for any \(f\) [L]
• We cannot find a maximal matching in \(o(\Delta) + O(\log^* n)\) rounds [BBHORS]
• We cannot find a maximal matching in \(o(\Delta)\) rounds in bipartite graphs [BBHORS]
• We cannot find a maximal fractional matching in \(o(\Delta)\) rounds [GHS]
• We cannot find a maximal fractional matching in \(o(\log \Delta/\log \log \Delta) + O(\log^* n)\) rounds, even in bipartite graphs [KMW]

Here are some examples of concrete questions:

• Can we find a maximal fractional matching in \(o(\Delta) + O(\log^* n)\) rounds?
• Can we find a maximal fractional matching in \(o(\Delta)\) rounds in bipartite graphs?

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:

• This is decidable and easy for problems without inputs on paths [CSS] [BHKLÖPRSU]
• This is decidable and easy for problems without inputs in rooted regular trees [BBCOSS]
• This is decidable but PSPACE-hard for problems with inputs on paths [BBCORS]
• This is undecidable for problems without inputs in grids [NS] [BHKLÖPRSU]

Here are some examples of concrete questions:

• Is this decidable for problems with inputs in unrooted trees, for deterministic LOCAL?
• Is this decidable for problems with inputs in unrooted trees, for randomized LOCAL?

Quantum-LOCAL model

For definitions, see [GKM] [AF].

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

• In the classical deterministic and randomized LOCAL models (see above), 3-coloring is not possible in \(o(\log^* n)\) rounds [L] [N]
• In the non-signaling model (see below), 3-coloring is possible with locality \(O(1)\) [HL]
• Quantum-LOCAL is sandwiched between the classical LOCAL model and the non-signaling model [GKM]

Here are some examples of concrete questions:

• Is it possible to 3-color a cycle in \(o(\log^* n)\) rounds in the quantum-LOCAL model?
• Is it possible to 3-color a cycle in \(O(1)\) rounds in the quantum-LOCAL model?

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:

• There is a graph problem that asymptotically separates quantum-LOCAL and classical randomized LOCAL, but this problem is very global [LNR]

Here are some examples of concrete questions:

• Does there exist any LCL problem with complexity \(O(1)\) in quantum-LOCAL and complexity \(\omega(1)\) in randomized LOCAL?
• Does there exist any LCL problem with complexity \(O(1)\) in quantum-LOCAL and complexity \(\Omega(\log n)\) in randomized LOCAL?
• Can we say anything nontrivial about the structure of the landscape of LCL complexities in quantum-LOCAL?

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:

• There is a finitely dependent distribution of 3-colorings in paths and cycles, and therefore 3-coloring is possible with locality \(O(1)\) in the non-signaling model [HL]
• In the classical LOCAL model, 3-coloring in rooted trees is asymptotically as easy as 3-coloring paths and cycles [GPS]

Here are some examples of concrete questions:

• Does there exist a finitely dependent distribution of 3-colorings in rooted trees?
• Is 3-coloring possible with locality \(O(1)\) in the non-signaling model?

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:

• Does there exist any LCL problem with locality \(O(1)\) in the non-signaling model and round complexity \(\omega(1)\) in quantum-LOCAL?
• Does there exist any LCL problem with locality \(O(1)\) in the non-signaling model and round complexity \(\omega(\log^* n)\) in classical deterministic LOCAL?

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:

• We cannot find a maximal matching in \(o(\Delta)\) rounds in bipartite graphs, and therefore we cannot find it with \(o(\Delta)\) volume [BBHORS]
• We can find a maximal matching in \(O(\Delta)\) rounds in bipartite graphs, and therefore we can find it with \(\Delta^{O(\Delta)}\) volume [HKP]

Here are some examples of concrete questions:

• Can we find a maximal matching in bipartite graphs with \(O(\Delta)\) volume?
• Can we find a maximal matching in bipartite graphs with \(\operatorname{poly}(\Delta)\) volume?

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:

• There is no LCL problem with deterministic volume between \(\omega(1)\) and \(o(\log^* n)\) [GRB]
• There is no LCL problem with deterministic volume between \(\omega(\log^* n)\) and \(o(\log n)\) [RS]
• There is no LCL problem with randomized volume between \(\omega(\log^* n)\) and \(o(\sqrt{\log n})\) [GRB]
• There are LCL problems with deterministic volumes \(O(1)\), \(\Theta(\log^* n)\), and \(\Theta(n)\) [RS]
• There are LCL problems with randomized volumes such as \(\Theta(\log n)\) and \(\tilde{\Theta}(\sqrt{n})\) [RS]

Here are some examples of concrete questions:

• Is there any LCL problem with deterministic volume between \(\omega(\log^* n)\) and \(o(n)\)?
• Is there any LCL problem with randomized volume between \(\omega(\log^* n)\) and \(o(\log n)\)?

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:

• LOCAL \(\subseteq\) dynamic-LOCAL \(\subseteq\) online-LOCAL [AELMSS]
• In paths, cycles, and rooted regular trees, coloring in online-LOCAL and dynamic-LOCAL is almost as hard as coloring in LOCAL; in particular, locality \(O(1)\) in online-LOCAL or dynamic-LOCAL implies locality \(O(\log^* n)\) in LOCAL [AELMSS]
• In unrooted trees, grids, and bipartite graphs, 3-coloring can be solved with locality \(O(\log n)\) [AELMSS]

Here are some examples of concrete questions:

• Can we find a 3-coloring in unrooted trees with locality \(O(1)\) in dynamic-LOCAL?
• Can we find a 3-coloring in bipartite graphs with locality \(O(\log n)\) in dynamic-LOCAL?
• Can we find a 3-coloring in bipartite graphs with locality \(O(1)\) in online-LOCAL?

  Latest news in December 2023: This is not possible, see [CMNYY] for a lower-bound proof! The locality of 3-coloring in grids and bipartite graphs is \(\Theta(\log n)\).

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:

• We can separate LOCAL vs. dynamic-LOCAL using problems like weak reconstruction and cycle detection, but they are not LCLs [AELMSS]
• We can separate dynamic-LOCAL vs. online-LOCAL using problems like component-wise leader election, but they are not LCLs [AELMSS]
• We can separate LOCAL vs. online-LOCAL using 3-coloring in trees, grids, or bipartite graphs, but each of them involves a promise (e.g. “the input is a bipartite graph”) [AELMSS]
• We can separate LOCAL vs. dynamic-LOCAL using 3-coloring in paths, but this only gives a difference between \(\Theta(\log^* n)\) vs. \(O(1)\) [AELMSS]

Here are some examples of concrete questions:

• Is there a promise-free LCL problem with complexity \(\Omega(n)\) in LOCAL and complexity \(O(1)\) in dynamic-LOCAL?
• Is there a promise-free LCL problem with complexity \(\Omega(n)\) in dynamic-LOCAL and complexity \(O(1)\) in online-LOCAL?

Acknowledgements

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