Constraints 𝒞 Abstract Is a LOCAL algorithm computable? Antonio Cruciani \cdot Aalto University, Finland Avinandan Das \cdot Aalto University, Finland Massimo Equi \cdot Aalto University, Finland Henrik Lievonen \cdot Aalto University, Finland Diep Luong-Le \cdot Columbia University, United States Augusto Modanese \cdot CISPA Helmholtz Center for Information Security, Germany Jukka Suomela \cdot Aalto University, Finland 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. We show that this question matters even for locally checkable labeling problems (LCLs), perhaps the most widely studied family of problems in the context of the LOCAL model. Furthermore, we show that assumptions about computability are directly connected to another aspect already recognized as highly relevant: whether we have any knowledge of n , the size of the graph. Concretely, we show that there is an LCL problem \Pi with the following properties: 1. \Pi can be solved in O(\regularlog n) rounds if the LOCAL model is uncomputable. 2. \Pi can be solved in O(\regularlog n) rounds in the computable model if we know any upper bound on n . 3. \Pi requires \Omega(\sqrt{n}) rounds in the computable model if we do not know anything about n . We also show that the connection between computability and knowledge of n holds in general: for any LCL problem \Pi , if you have any bound on n , then \Pi has the same round complexity in the computable and uncomputable models. 1 Introduction There is no single, universally-agreed-on definition of the “standard” \operatorname{\mathsf{LOCAL}} model of distributed computing. And when a paper introduces the \operatorname{\mathsf{LOCAL}} model, some aspects are often left unspecified, or the definition might even be self-contradictory. A case in point is assumptions related to computability . By definition, the local state of a node after T rounds is some function f of its radius- T neighborhood—but is this function a computable function, or an arbitrary function? Many key papers state that one can use any function, without any restrictions related to computability [ 19 , 20 , 15 ] . At the same time, papers often use words such as “processor” [ 19 , 20 ] to refer to individual nodes, as if they would be implementable as real-world computers that are restricted to computable functions. Some papers make it explicit that nodes are computationally bounded [ 17 ] . Finally, there are some rare papers such as [ 12 ] that explicitly acknowledge that one can define both the computable and uncomputable version of the model. Many papers leave computability assumptions somewhat vague and open to interpretation, and when explicitly asked about this aspect, there is disagreement among the experts on whether the computable or uncomputable version is the “right” one. Yet what many of our colleagues seem to assume is that this aspect is not particularly relevant from the perspective of problems of interest to them. The issue gets increasingly important (and confusing) with the emerging area of distributed quantum computing. When we define the quantum version of the \operatorname{\mathsf{LOCAL}} model [ 13 , 1 ] , the natural formalization is something equivalent to quantum circuits or quantum Turing machines, which is necessarily computable—there is no quantum analogue of mapping radius- T neighborhoods to local outputs. Combining this with a conventional uncomputable definition of the classical \operatorname{\mathsf{LOCAL}} model would lead to paradoxical results: quantum- \operatorname{\mathsf{LOCAL}} would be weaker than classical \operatorname{\mathsf{LOCAL}} . What we show in this work is that assumptions related to computability are indeed critical even if we focus on problems and questions commonly studied in the context of the \operatorname{\mathsf{LOCAL}} model. 1.1 Locally Checkable Labelings Perhaps the most popular (and most restrictive) formal definition for a class of “reasonable” graph problems in this context is the family of locally checkable labeling problems , or LCLs, first introduced by Naor and Stockmeyer in 1995 [ 20 ] . These are problems that can be specified by giving a finite set of valid labeled local neighborhoods. There is a long line of research that has culminated in a near-complete classification of LCL problems in the \operatorname{\mathsf{LOCAL}} model for general graphs, see e.g. [ 10 , 21 , 19 , 20 , 6 , 11 , 14 , 5 , 8 , 7 , 23 , 2 , 3 , 25 , 9 , 16 ] . What makes LCL problems particularly nice and clean from the perspective of computability issues is that for any LCL problem \Pi , there are Turing machines that solve both of these tasks: 1. Given a graph G and output labeling f , decide if f is a valid solution of \Pi in G . 2. Given a graph G , find a feasible solution f of \Pi in G . In particular, there is no LCL where merely solving the task is uncomputable; if you can solve a task with full information about G in uncomputable- \operatorname{\mathsf{LOCAL}} , you can do the same in computable- \operatorname{\mathsf{LOCAL}} . Intuitively, LCLs should not care about computability issues. Now what we would like to do is to formalize this intuition and prove that we can safely ignore all issues regarding computability in the context of LCL problems; we would like to show that whatever is the complexity of an LCL in uncomputable- \operatorname{\mathsf{LOCAL}} , it is (at least asymptotically) the same in computable- \operatorname{\mathsf{LOCAL}} . This would mean that the numerous results on LCLs from prior work are compatible with each other regardless of what the specific paper assumes about computability. Unfortunately, as we will show in this work, this is not the case! 1.2 Contribution 1: Separation Our main contribution is this: we show that there exists an LCL problem \Pi such that: • in computable- \operatorname{\mathsf{LOCAL}} , any algorithm that solves \Pi requires \Omega(\sqrt{n}) rounds, • in uncomputable- \operatorname{\mathsf{LOCAL}} , there is an algorithm that solves \Pi in O(\regularlog n) rounds. Our key take-home message is that assumptions on computability are of crucial importance already in the study of LCL problems; such issues cannot be safely ignored, results on the complexity landscape cannot be automatically ported between computable and uncomputable worlds, and this aspect needs to be made explicit. (An equally valid interpretation of our work is that LCL problems are a poor proxy for “reasonable” graph problems, as we run into issues of computability, which we should never encounter in reasonable graph problems. But currently no good alternatives exist.) 1.3 Contribution 2: Equivalences To fully explain our contributions, it is necessary to draw attention to another subtle issue of the \operatorname{\mathsf{LOCAL}} model that tends to get swept under the carpet: what do we know about n , the size of the input. We will consider three cases that suffice to make the point: 1. no auxiliary information, 2. all nodes receive as input the same value N , and we promise that n\leq N , 3. all nodes receive as input the same value N , and we promise that n\leq N\leq f(n) for some fixed, globally-known computable function f . Combining this with models computable- \operatorname{\mathsf{LOCAL}} and uncomputable- \operatorname{\mathsf{LOCAL}} , we arrive at six combinations that might be all distinct. Yet we show that the landscape shown in Table 1 emerges; six models collapse to three classes {\mathsf{I}}<{\mathsf{II}}\leq{\mathsf{III}} . Table 1 : For LCL problems, our six models fall in three classes with {\mathsf{I}}<{\color[rgb]{0.9492,0.4102,0.1406}{\mathsf{II}}}\leq{\color[rgb]{0,0.5352,0.8008}{\mathsf{III}}} . computable uncomputable \operatorname{\mathsf{LOCAL}} \operatorname{\mathsf{LOCAL}} no auxiliary information {\mathsf{I}} {\mathsf{II}} bound n\leq N {\mathsf{II}} {\mathsf{II}} bound n\leq N\leq f(n) {\mathsf{III}} {\mathsf{III}} Our LCL problem \Pi serves to separate classes {\mathsf{I}} and {\mathsf{II}} . However, what seems counterintuitive is that all of these three models in class {\mathsf{II}} are equally strong for LCLs (and beyond), at least when we restrict ourselves to computable time complexities: • uncomputable- \operatorname{\mathsf{LOCAL}} , with no auxiliary information, • uncomputable- \operatorname{\mathsf{LOCAL}} , with a bound n\leq N , • computable- \operatorname{\mathsf{LOCAL}} , with a bound n\leq N . We also show that these two models in {\mathsf{III}} are equally strong for LCLs (and beyond), for any computable bound f , again when we restrict ourselves to computable time complexities: • uncomputable- \operatorname{\mathsf{LOCAL}} , with a bound n\leq N\leq f(n) , • computable- \operatorname{\mathsf{LOCAL}} , with a bound n\leq N\leq f(n) . This brings some good news: it turns out that numerous papers that have studied LCLs in the \operatorname{\mathsf{LOCAL}} model have assumed (explicitly or implicitly) that there is some information on n available, either exact knowledge of n or e.g. some linear or polynomial upper bound on n . What we show is that as long as some information on n is available, uncomputable and computable worlds collapse into a single model, and we can freely translate results between them. Finally, we draw attention to the following corollary of our work—these two models are distinct for LCLs: • computable- \operatorname{\mathsf{LOCAL}} , with no auxiliary information, • computable- \operatorname{\mathsf{LOCAL}} , with a bound n\leq N . In particular, our problem \Pi can be solved in O(\regularlog n) rounds in computable- \operatorname{\mathsf{LOCAL}} if we know any bound n\leq N , but it requires \Omega(\sqrt{n}) rounds in computable- \operatorname{\mathsf{LOCAL}} if we do not have such information. This result seems counterintuitive: our upper bound N might be arbitrarily high, say, the Ackermann function of n , or even the busy beaver [ 22 ] of n , which seems unhelpful, yet it can be so valuable that it suffices to lower the round complexity exponentially. 2 Technical Overview In this section, we give an overview of the techniques and key ideas that we use to prove our main results, and we also provide a road-map to the rest of this paper. Our separation result is presented in Section 4 , and our equivalence results are presented in Section 5 . 2.1 Separation Between Computable- \operatorname{\mathsf{LOCAL}} and Uncomputable- \operatorname{\mathsf{LOCAL}} First we discuss the proof for the separation between computable and uncomputable \operatorname{\mathsf{LOCAL}} where we are not given an upper bound N on the number of nodes. The proof is by a careful construction of an LCL problem \Pi that requires \Omega(\sqrt{n}) locality in computable- \operatorname{\mathsf{LOCAL}} but only \mathcal{O}(\regularlog n) in its uncomputable counterpart. Our separation is obtained by constructing a promise-free LCL \Pi , where each node outputs several components (or layers). The early layers can be seen as structure filters that either certify that the input graph has the intended backbone structure, or they produce a locally checkable error certificate that points to a structural violation. Only the nodes that successfully pass all the structural filters are required to solve the final “hard” layer. Formally, each structural layer \Pi_{i} is split into \Pi_{i}^{\mathrm{good}} and \Pi_{i}^{\mathrm{bad}} with disjoint output alphabets. Intuitively • \Pi_{i}^{\mathrm{good}} The structure “looks” correct and nodes output a fixed label. • \Pi_{i}^{\mathrm{bad}} . The structure is “broken” and nodes output an error pointer that locally routes to a witness or failure. We then compose these layers so that the subsequent layers’ constraints are enforced only inside the region certified as good so far. The backbone decomposition. The overall problem is represented as a composition of five layers \Pi=\Pi_{\mathrm{tree}}\otimes\Pi_{\mathrm{row}}\otimes\Pi_{\mathrm{grid}}\otimes\Pi_{\mathrm{Turing}}\otimes\Pi_{\mathrm{consensus}} Each layer has a good and bad behavior: • \Pi_{\mathrm{tree}} certifies a tree-like auxiliary structure by marking nodes as T , or else outputs a local pointer to a structural error. • \Pi_{\mathrm{row}} certifies nodes marked with G form rows that are connected to trees. • \Pi_{\mathrm{grid}} certifies that the rows together form a grid-like structure. • \Pi_{\mathrm{Turing}} ensures that the labels on the grid encode an execution of a Turing machine. • \Pi_{\mathrm{consensus}} is the hard layer which gives us the separation. In effect, the rows of the grid need to predict the outcome of the encoded Turing machine. The growing grid structure. The concrete structure that we would like to ensure is what we refer to as a growing grid . This is an oriented grid where rows are neatly aligned (see Figure 1(a) ) and with the additional property that consecutive rows differ in length by exactly one. Since (virtually) every row has \Theta(\sqrt{n}) nodes, to enable sublinear-time certification inside a row, each row is also equipped with an attached tree-like structure with \mathcal{O}(\regularlog n) diameter (see Figure 1(b) ). The tree structure allows each row to operate as a joint computational unit that is coordinated by the node at the root of the corresponding tree. The hard problem \Pi_{\mathrm{Turing}} . Inside the certified grid region, input labels encode a computation of a universal Turing machine U : each row encodes a configuration (tape symbols, head position and state), and local constraints check that consecutive rows represent valid transitions of U . If the encoding is inconsistent, nodes can locally point to an error, partitioning the grid into valid regions separated by error regions. The crucial final constraint is a consistency requirement: whenever a region contains a halting configuration, nodes in that region must output a globally consistent bit indicating whether the halting state is accepting or rejecting. A subtle point is that we must use a machine U that has halting accept and reject states; see the discussion further below for details. Uncomputable- \operatorname{\mathsf{LOCAL}} solves \Pi in \mathcal{O}(\regularlog n) rounds. In uncomputable- \operatorname{\mathsf{LOCAL}} we may assume access to an oracle H that, given a configuration of the universal Turing machine U , decides whether it halts or not as well as whether the halting state is accepting or rejecting. On a valid grid instance, the root of the tree attached to a row collects the entire row’s encoding in \mathcal{O}(\regularlog n) rounds, determines the configuration encoded in the row, and queries H . Given the oracle’s answer, the root node sets the output for the nodes it controls to the final state of U or, if the configuration is not halting, to 0 . Since all the rows access the same oracle and the universal Turing machine is deterministic, the output of all rows is consistent across the same component of the input graph. Computable- \operatorname{\mathsf{LOCAL}} needs \Omega(\sqrt{n}) rounds. The lower bound relies on a diagonalization argument. Assume that there is a computable- \operatorname{\mathsf{LOCAL}} algorithm \mathcal{A} that purportedly solves \Pi in o(\sqrt{n}) rounds. On our growing-grid instances G_{k} with k rows (and thus \Theta(k^{2}) nodes), such a locality is o(k) ; hence a node in a fixed early layer cannot see the bottom boundary of the grid. In fact, we can show that, for large enough values of k , nodes in these early layers must commit to an output in a constant number of rounds . We exploit this by constructing a Turing machine T_{\mathcal{A}} that, given an input x , simulates \mathcal{A} on G_{k} for a sufficiently large k and produces the output bit of \mathcal{A} on the row with configuration corresponding to x . Notice that \mathcal{A} always halts, hence so does T_{\mathcal{A}} . Finally, we feed T_{\mathcal{A}} to a diagonalizer D that, on input \langle T_{\mathcal{A}}\rangle , outputs the opposite bit whenever T_{\mathcal{A}} halts. Thus, given the input x=(\langle D\rangle,\langle T_{\mathcal{A}}\rangle) , the nodes of \mathcal{A} in the row corresponding to x will produce the opposite of what is required. It follows that \mathcal{A} fails to solve \Pi , implying its complexity in computable- \operatorname{\mathsf{LOCAL}} is \Omega(\sqrt{n}) . A remark about the specification of the problem output. Let us take a closer look at the condition for the output bit we ask for in our problem \Pi_{\mathrm{Turing}} : 1. If U halts in the final configuration of the growing grid, then output 0 if it rejects or 1 if it accepts. 2. Otherwise (i.e., if U has not halted by the final configuration), then output either 0 or 1 consistently. Interestingly, this condition must be very carefully chosen. For instance, suppose we leave the problem description as is and only replace the second point with the following: 2a. Otherwise (i.e., if U has not halted by the final configuration), then output 0 . As it turns out, this breaks the \mathcal{O}(\regularlog n) upper bound : Of course, with access to an uncomputable oracle, we can still correctly determine whether U halts or not; however, the issue is that we must also determine if the input grid is large enough to contain the entire trace of U until it halts, which inevitably requires inspecting the entire grid. A much more counterintuitive situation applies to the first of the two requirements for the output bit. It is a standard result in computability theory that, without restriction, we may define Turing machines such that they are only allowed to halt if they are in an accepting state (and enter an infinite loop whenever an input should be rejected). Being aware of this, we might be tempted to replace our U that has explicit accept and reject states with another universal U^{\prime} that only halts in an accepting state. This simplifies the first of the two items above to the following: 1a. If U^{\prime} halts in the final configuration of the growing grid, then output 1 everywhere. Surprisingly, this now breaks the lower bound : Together with the original second item, the resulting problem is trivial since one can always output 1 no matter what U^{\prime} does. Replacing 2 with 2a does not remedy this as we then run into the same issue with the upper bound as before (i.e., we fail to obtain an \mathcal{O}(\regularlog n) algorithm in uncomputable- \operatorname{\mathsf{LOCAL}} ). Hence it is crucial that our U has both halting accept and reject states , unlike what our intuition from computability theory might suggest. An alternative upper bound in computable- \operatorname{\mathsf{LOCAL}} with an upper bound on n . As an addendum, we also describe a strategy for solving \Pi in computable- \operatorname{\mathsf{LOCAL}} with \mathcal{O}(\regularlog n) when an upper bound N (no matter how bad) on n\leq N is given. It is true that one can use our equivalence results to obtain such an algorithm, but it is instructive to come up with a direct strategy to grasp why the knowledge of N makes such a big difference. The idea is to proceed as in the uncomputable- \operatorname{\mathsf{LOCAL}} algorithm but replace the oracle H with a computable procedure. More specifically, using N we infer a maximal number of steps t_{N} that U can run for; otherwise its trace would not fit into the input instance we are given. Then we can simulate U until t_{N} steps have elapsed and, if U has not halted yet, safely output 0 on all nodes. The point is that, given N , we have a bound on how large our instance can be (even if it is arbitrarily bad!), which allows us to circumvent the computability issues; without N , we cannot know how large our instance actually is , and thus it might always be large enough to contain the entire trace of U until it halts—which we cannot tell for sure without inspecting the whole instance. 2.2 Equivalence Results Next we discuss our equivalence results. Recall there are two equivalences that we prove: 1. between computable- \operatorname{\mathsf{LOCAL}} with an upper bound N\geq n (where possibly also N\leq f(n) for some computable f ) and uncomputable- \operatorname{\mathsf{LOCAL}} ; and 2. uncomputable- \operatorname{\mathsf{LOCAL}} with and without such an upper bound N . Before we turn to these equivalences, we first discuss the concept of a maximally safe neighborhood , which is used in both proofs. Maximally safe neighborhoods. In the ball-growing view of \operatorname{\mathsf{LOCAL}} model, a deterministic algorithm can be described by a function that given the currently gathered rooted neighborhood N^{t}(v) and the current radius t , either outputs a label or returns a sentinel \bot to indicate “keep exploring”; the node halts at the first radius t for which the function returns a label. A time bound T(n) means that on every n -node network, every node must halt by round T(n) . A subtle detail is that nodes do not know n . Hence, whether a node is allowed to still be running at round t must be justified purely from its local view. This motivates a notion of when a radius- t view is consistent with a global bound T . 1 Informal. For a network G and a node v\in V(G) , we say t\in\mathbb{N}_{0} is T -safe for v if there is no network G^{\prime} and v^{\prime}\in V(G^{\prime}) such that the t -neighborhoods rooted at v and v^{\prime} are isomorphic and t>T(\lvert V(G^{\prime})\rvert) . In addition, t is said to be maximally T -safe for v if it is maximal with this property (i.e., t is safe but t+1 is not). The intuition behind Definition 1 is that if N^{t}(v) is T -safe, then “still not having halted before round t ” is not in conflict with the promise that all n^{\prime} -node instances must halt by round T(n^{\prime}) . Indeed, the same local situation N^{t}(v) cannot occur in any instance whose time bound T(n^{\prime}) is already strictly less than t . Conversely, if a new view at radius t could also occur inside some smaller instance with T(n^{\prime})1 , then (1,1) is not the right-most node of its row, hence it has an \mathrm{E} -neighbor by \mathcal{C}_{\mathrm{goodRow}} , and therefore \{(1,1),(1,2)\}\in E(G) . If h>1 and \ell>1 , then (1,1) is not right-most, so by rule 2 of \mathcal{C}_{\mathrm{goodGrid}} it has a \mathrm{S} -neighbor, and hence \{(1,1),(2,1)\}\in E(G) . 2. Inductive step. Assume the statement holds for all (i^{\prime},j^{\prime})\prec(i,j) . (a) If j<\ell+i-1 , then (i,j) is not right-most, hence it has an \mathrm{E} -half-edge. Applying rule 3 at (i,j) yields f((i,j),\mathrm{E})=(i,j+1) , and therefore \{(i,j),(i,j+1)\}\in E(G) . (b) If ii . • The inputs are chosen so that all nodes, except for nodes on constantly-many layers close to layers 1 and k , must solve \Pi_{\mathrm{goodGrid}} . In addition, we define a binary input x with length m\leq k to G_{k} . Let t_{x}\in\mathbb{N}_{0}\cup\{\infty\} be the number of steps that U runs for when given input x . Then x defines the rest of the inputs to the nodes in G_{k} as follows: – For the row nodes that are in a layer preceding the m -th one, the input is o throughout the row. – For the row nodes in the m -th layer, place x written from left to right on that row, with the Turing machine head placed on the first symbol of x . – For the row nodes that are in a layer subsequent to the m -th one, we extend the configuration inductively starting from the m -th layer by applying the transition function specified by U . Hence the m^{\prime} -th layer is the (m^{\prime}-m) -th configuration that U reaches starting from m . If m^{\prime}>t_{x} , then we place the halting configuration across the row. Notice that G_{k} has \Theta(k^{2}) nodes. Furthermore, we have that G_{k} and G_{k^{\prime}} are identical in the first \min\{k,k^{\prime}\} layers. We now fix a computable distributed algorithm \mathcal{A} with locality o(\sqrt{n}) . Observe that, together with how we constructed G_{k} , this implies we can make the following statement: For every given m\in\mathbb{N}_{+} , there is a constant k_{0}=k_{0}(m)>m such that, for any k\geq k_{0} , when we run \mathcal{A} on G_{k} with any input x of our choosing, all the nodes in the m -th layer of G_{k} stop their operation and produce an output within the first k-m-1 rounds. In particular, this means that the nodes in layer m do not see farther than the first k-1 layers in G_{k} even as k goes to infinity. Thus the number of rounds it takes for these nodes to commit to an output is constant and independent of k , at least for large enough values of k . For the sake of uniqueness, we fix k_{0} to be the least such value for which this statement holds. In addition to the above, we assume that \mathcal{A} always produces a consistent output to \Pi_{\mathrm{Turing}} in each layer (i.e., there are no disagreements concerning the output bit) since otherwise the claim is trivial. With this in place, we now define a Turing machine T as follows: 1. Given an input x of length m , iterate over k to determine the least k>m for which, when we run \mathcal{A} (which is computable) on G_{k} , the nodes in the m -th layer of G_{k} do not see farther than the first k-1 layers, no matter what input x is chosen for G_{k} . By construction, the value computed by T will equal k_{0} . 2. Construct G_{k_{0}} with input x . 3. Simulate the operation of \mathcal{A} on G_{k_{0}} and determine what bit b the nodes of \mathcal{A} produce in their output to \Pi_{\mathrm{Turing}} in the m -th layer. 4. Output b . Note that the first step always terminates due to the existence of k_{0} , and so T always halts. Finally, let D be the Turing machine from Section 4.3 , x_{T}=(\langle D\rangle,\langle T\rangle) , and m=\lvert x_{T}\rvert . Consider the behavior of \mathcal{A} on the instance G_{k_{0}} with input x_{T} . Since T always halts, then so does D on input x_{T} . Whatever bit the nodes of \mathcal{A} output in the m -th layer of G_{k_{0}} is, by construction of T , identical to T(x_{T}) . However, the output of U on x_{T} is identical to D(x_{T})=1-T(x_{T}) . Hence \mathcal{A} fails to solve the problem \Pi . ∎ This concludes the proof of Theorem 1 . 5 Equivalence Results In this section we prove our equivalence results. First, we show that once nodes are provided with any global upper bound N on the network size (and optionally a promise of the form N\leq f(n) for a fixed computable f ), the gap between computable and uncomputable \operatorname{\mathsf{LOCAL}} vanishes: every uncomputable- \operatorname{\mathsf{LOCAL}} T -round algorithm can be converted into a computable- \operatorname{\mathsf{LOCAL}} algorithm with the same locality. Second, we show that in uncomputable \operatorname{\mathsf{LOCAL}} the bound N is in fact unnecessary: from a family \{\mathcal{A}_{N}\} of T -round algorithms that work for all n\leq N , we construct a single bound-free algorithm that still runs in at most T(n) rounds and agrees with \mathcal{A}_{N} for a suitable choice of N . Both arguments are organized around the notion of maximally T -safe neighborhoods that we describe in the following subsection. 5.1 Maximally Safe Neighborhoods—and How to Find Them Here we discuss the concept of maximally safe neighborhood, a useful tool that we will use in our equivalence proofs. Note that the concept depends only on a given complexity function T and is independent of any particular algorithm under consideration. 10 . Let T\colon\mathbb{N}_{+}\to\mathbb{N}_{0} be a function and \mathcal{G} a class of graphs. For a network (G,x,\mathtt{deg},\mathtt{id},\{p_{v}\}) with G\in\mathcal{G} and a node v\in V(G) , we say t\in\mathbb{N}_{0} is T -safe for v in \mathcal{G} if there is no network (G^{\prime},x^{\prime},\mathtt{deg}^{\prime},\mathtt{id}^{\prime},\{p_{v}^{\prime}\}) with G^{\prime}\in\mathcal{G} and v^{\prime}\in V(G^{\prime}) such that the t -neighborhoods rooted at v and v^{\prime} are isomorphic and t>T(\lvert V(G^{\prime})\rvert) . Moreover, we say t is maximally T -safe for v if it is maximal with this property (i.e., t is safe but t+1 is not). Without ambiguity, we extend these notions to the rooted neighborhoods themselves; that is, if t is (maximally) T -safe for v , then we say that \mathcal{N}^{t}(v) is also (maximally) T -safe . Note that, if we fix v , then there is always a maximally T -safe t . This is because we may always pick G^{\prime}=G , x^{\prime}=x , \mathtt{id}^{\prime}=\mathtt{id} , and v^{\prime}=v in the condition above, in which case the only non-trivial requirement is that t>T(\lvert V(G)\rvert) , which must hold for all but finitely many t . {lemma} Let T be non-decreasing and computable, and let \mathcal{G} be an enumerable class of graphs. Then, given a rooted neighborhood X of radius t\in\mathbb{N}_{0} , it is decidable if X is maximally T -safe or not. Since T is non-decreasing, it can be argued that there are only finitely many counter-examples to test in order to check whether X is maximally T -safe or not. That being said, we must first deal with some technicalities concerning the function T . Proof. Let X be given. Since T is non-decreasing, there are two options for its behavior relative to the value t : 1. Either there is N\in\mathbb{N}_{+} such that t0 given an infinite set S_{i-1} , inspect the multiset \mathcal{M}_{i}:=\{\mathcal{A}_{N}^{\prime}(i)\mid N\in S_{i-1}\} . By Construction step 1: sandboxing the upper-bound algorithms. , at most the first N_{i}-1 indices can map to \bot . Hence, \bot appears only finitely many times. After discarding those finitely many \bot values, the multiset is still infinite and now contains only labels from the finite set \Sigma_{\mathrm{out}} . By the infinite pigeonhole principle, at least one output label occurs infinitely many times. Let it be s_{i} . Define S_{i}:=\{N\in S_{i-1}\mid\mathcal{A}_{N}^{\prime}(i)=s_{i}\} . Since the class associated with s_{i} is infinite, the new set S_{i} is also infinite. Hence, every \mathcal{A}_{N}^{\prime} with N\in S_{i} returns the same label s_{i} in the neighborhood X_{i}\subseteq G . Construction step 3: the bound-free algorithm \mathcal{B} . We are now ready to define the algorithm \mathcal{B} that does not use any information about the number of nodes in the network. On each node v , \mathcal{B} does the following: 1. Collect the view until it becomes a maximally T -safe neighborhood Y_{v}=X_{i} ; 2. Output the pre-selected label s_{i} . Clearly, the first step is completed within T(n) rounds, so \mathcal{B} satisfies the time bound. Correctness. Fix an n -node network (G,x,\mathtt{deg},\mathtt{id},\{p_{v}\}) . For each node v\in V(G) , let Y_{v}\cong X_{i} be its maximally T -safe neighborhood. In addition, let I=\left\{i\mid\text{$\exists v$ with $Y_{v}\cong X_{i}$}\right\} and i^{\star}=\max I . From the stabilization argument (step 2) we have infinite nested sets S_{0}\supseteq S_{1}\supseteq S_{2}\supseteq\cdots with the property that, for all N\in S_{i} , the sandboxed algorithm \mathcal{A}_{N}^{\prime}(i) outputs the stabilized label s_{i} on X_{i} . Notice that S_{i^{\star}} is infinite; choose N\in S_{i^{\star}} , with N\geq n . Fix any node v with Y_{v}\cong X_{i} (so i\in I and i\leq i^{\star} ). By nestedness, S_{i^{\star}}\subseteq S_{i} , hence our chosen N\in S_{i} . Therefore, \mathcal{A}_{N}^{\prime}(i)=s_{i}\neq\bot . By the definition of the sandbox, whenever \mathcal{A}_{N}^{\prime}(i)\neq\bot , it equals the output that the original algorithm \mathcal{A}_{N} gives on the root of a node whose T -round view is X_{i} . Hence, at every node v we have that algorithm \mathcal{B} produces s_{i} as \mathcal{A}_{N}^{\prime}(i) and \mathcal{A}_{N} . Thus the labeling of \mathcal{B} on G coincides node-by-node with that of \mathcal{A}_{N} . Since n\leq N , algorithm \mathcal{A}_{N} is correct on G ; therefore \mathcal{B} is also correct.∎ Consequently, we can claim that in uncomputable- \operatorname{\mathsf{LOCAL}} knowing an upper bound N on the number of nodes in the graph does not provide any advantage for deterministic algorithms in solving LCL problems, formally: {corollary} In uncomputable- \operatorname{\mathsf{LOCAL}} , giving all nodes an upper bound N on n=|V(G)| provides no advantage for deterministic algorithms solving LCL problems. Proof. Suppose an LCL problem \Pi is solvable in uncomputable- \operatorname{\mathsf{LOCAL}} with access to an upper bound N on the number of nodes in the considered network (G,x,\mathtt{deg},\mathtt{id},\{p_{v}\}) . Then there exists a family \{\mathcal{A}_{N}\} of algorithms as in Theorem 4 that solve \Pi in T(n) rounds. By the theorem, there exists a bound-free algorithm \mathcal{B} that solves \Pi in the same number of rounds as well. ∎