What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing

The question of "what can be computed locally?" lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993, Edsger W. Dijkstra Prize in Distributed Computing 2025), this question is undecidable, even for graph problems whose solutions can be checked locally. In this paper, we adopt a novel perspective on the question, by asking for which classes Π of problems, and for which classes G of graphs, all problems in Π can be solved efficiently in a distributed manner in all graphs of G. This paper focuses on two natural candidates for such an approach, namely the class of problems expressible in first-order logic (FO), because they possess an intrinsic form of locality thanks to Gaifman's theorem, and the class of graphs with bounded expansion, because they form a large class of graphs encompassing, e.g., planar, bounded-genus, bounded-treewidth, and bounded-degree graphs, as well as graphs excluding a fixed minor or topological minor, sparse Erdös--Rényi graphs (a.a.s.), and several network models such as stochastic block models for suitable parameter ranges. The starting point of our work is the decade-old open question of Nešetřil and Ossona de Mendez (Distributed Computing 2016) on the distributed complexity of local FO formulas on graphs of bounded expansion, in the standard CONGEST model of distributed computing. Recall that a formula φ(x) is local if the satisfaction of φ(x) depends only on the r-neighborhood of its free variable x, for some fixed r. For instance, the formula "x belongs to a triangle" is local. We resolve the open problem of Nešetřil and Ossona de Mendez positively by showing that, for every local FO formula φ(x), and for every graph class G of bounded expansion, there exists a deterministic algorithm that identifies, for every n-vertex graph G ∈ G, all vertices v of G such that G ⊨ φ(v), in O(log n) rounds. The requirement of locality is unavoidable, as even the simple FO formula "there exist two vertices of degree 3" requires Ω(D) rounds in CONGEST, even on trees of diameter D. Nevertheless, we establish a second result, which goes beyond the question of Nešetřil and Ossona de Mendez. We show that O(D + log n) rounds are sufficient for deciding any FO formula φ on graphs of bounded expansion. That is, the overhead to be paid over the diameter is just O(log n). We underline that the techniques behind our two distributed "meta-theorems" extend to distributed counting, optimization, and certification problems. Our results are tight in several ways. Regarding the choice of the graph class G, we show that deciding FO formulas may have high round complexity in CONGEST on larger classes of graphs, even if they remain sparse. For instance, the simple local FO formula expressing C6-freeness requires O (sqrt(n)) rounds to be decided in graphs of degeneracy 2 with constant diameter. Regarding the choice of the class Π of problems, we show that deciding problems expressible in monadic second-order (MSO) logic may have high round complexity in CONGEST, even in classes of graphs with bounded expansion. For example, deciding non-3-colorability requires O (n) rounds in bounded-degree graphs with logarithmic diameter.