Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context of distributed local decision, where the objective is to decide whether G has property P by having each node run a constant-time distributed decision algorithm. In a yes-instance all nodes should output yes, while in a no-instance at least one node should output no. Recently, (OPODIS 2012) gave several conditions under which identifiers are not needed, and they conjectured that identifiers are not needed in any decision problem. In the present work, we disprove the conjecture. More than that, we analyse two critical variations of the underlying model of distributed computing: (B): the size of the identifiers is bounded by a function of the size of the input network, (¬B): the identifiers are unbounded, (C): the nodes run a computable algorithm, (¬C): the nodes can compute any, possibly uncomputable function. While it is easy to see that under (¬B, ¬C) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and only if identifiers are present.
The purpose of this paper is a study of computation that can be done locally in a distributed network. By locally we mean within time (or distance) independent of the size of the network. In particular we are interested in algorithms that ore robust, i.e., perform well even if the underlying graph is not stable and links continuously fail and come-up. We introduce and study the happy coloring and orientation problem and show that it yields a robust local solution to the (d,m)-dining philosophers problem of Naor and Stockmeyer [17]. This problem is similar to the usual dining philosophers problem, except that each philosopher has access to d forks but needs only m of them to eat. We give a robust local solution if m spl les [d 2] (necessity of this inequality for any local solution was known previously). Two other problems we investigate are: (1) the amount of initial symmetry-breaking needed to solve certain problems locally (for example, our algorithms need considerably less symmetry-breaking than having a unique ID on each node), and (2) the single-step color reduction problem: given a coloring with c colors of the nodes of a graph, what is the smallest number of colors c' such that every node can recolor itself with one of c' colors as a function of its immediate neighborhood only. > The purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: There are nontrivial LCL problems that have local algorithms. There is a variant of the dining philosophers problem that can be solved locally. Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL has an algorithm that operates in a given time @math . Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor IDs).