Common definitions of the “standard” LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a computable function? So far, this distinction has been safe to neglect, since problems where it matters seem contrived and quite different from e.g. typical local graph problems studied in this context.

The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid.

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: 1. All LCL problems solvable with locality $O(\log^\star n)$ in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality $O(1)$. This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. 2. In rooted trees, if we can solve an LCL problem with locality $o(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^\star n)$ locality in quantum-LOCAL is not stronger than $O(\log^\star n)$ locality in classical LOCAL.

We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree $Δ$, any classical (deterministic or randomized) LOCAL model algorithm will require $Ω(Δ)$ rounds to solve the iterated GHZ problem, while the problem can be solved in $1$ round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires $Ω(Δ)$ rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.

In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm $\mathcal{A}$ that finds an $α$-approximation of some linear optimization problem $Π$ in $T$ communication rounds, we can construct a classical, deterministic LOCAL algorithm $\mathcal{A}'$ that finds an $α$-approximation of $Π$ in $T$ rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. Second, using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL also to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.

The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algorithms, - the quantum version of the LOCAL model, - finitely dependent distributions [e.g. Holroyd 2016], - any model that does not violate physical causality [Gavoille, Kosowski, Markiewicz, DISC 2009], - the SLOCAL model [Ghaffari, Kuhn, Maus, STOC 2017], and - the dynamic-LOCAL and online-LOCAL models [Akbari et al., ICALP 2023]. In general, the online-LOCAL model can be much stronger than the LOCAL model. For example, there are locally checkable labeling problems (LCLs) that can be solved with logarithmic locality in the online-LOCAL model but that require polynomial locality in the LOCAL model. However, in this work we show that in trees, many classes of LCL problems have the same locality in deterministic LOCAL and randomized online-LOCAL (and as a corollary across all the above-mentioned models). In particular, these classes of problems do not admit any distributed quantum advantage. We present a near-complete classification for the case of rooted regular trees. We also fully classify the super-logarithmic region in unrooted regular trees. Finally, we show that in general trees (rooted or unrooted, possibly irregular, possibly with input labels) problems that are global in deterministic LOCAL remain global also in the randomized online-LOCAL model.

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that:

In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a new model of computing, called the online-LOCAL model: the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node we get to see its radius-T neighborhood before choosing the output. We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-T neighborhood, its sequential counterpart SLOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-T neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models, with LOCAL being the weakest and online-LOCAL the strongest model. In general, all models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems studied in the context of distributed graph algorithms. We prove that for LCL problems in paths, cycles, and rooted trees, all models are roughly equivalent: the locality of any LCL problem falls in the same broad class - $O(\log^* n)$, $Θ(\log n)$, or $n^{Θ(1)}$ - in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model. We also show that this equivalence does not hold in general bipartite graphs. We provide an online-LOCAL algorithm with locality $O(\log n)$ for the $3$-coloring problem in bipartite graphs - this is a problem with locality $Ω(n^{1/2})$ in the LOCAL model and $Ω(n^{1/10})$ in the SLOCAL model.

One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most exponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions-it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.