  The issue of identifiers is crucial in distributed computing. Informally,
identities are used for tackling two of the fundamental difficulties that
areinherent to deterministic distributed computing, namely: (1) symmetry
breaking, and (2) topological information gathering. In the context of local
computation, i.e., when nodes can gather information only from nodes at bounded
distances, some insight regarding the role of identities has been established.
For instance, it was shown that, for large classes of construction problems,
the role of the identities can be rather small. However, for theidentities to
play no role, some other kinds of mechanisms for breaking symmetry must be
employed, such as edge-labeling or sense of direction. When it comes to local
distributed decision problems, the specification of the decision task does not
seem to involve symmetry breaking. Therefore, it is expected that, assuming
nodes can gather sufficient information about their neighborhood, one could get
rid of the identities, without employing extra mechanisms for breaking
symmetry. We tackle this question in the framework of the $\local$ model. Let
$\LD$ be the class of all problems that can be decided in a constant number of
rounds in the $\local$ model. Similarly, let $\LD^*$ be the class of all
problems that can be decided at constant cost in the anonymous variant of the
$\local$ model, in which nodes have no identities, but each node can get access
to the (anonymous) ball of radius $t$ around it, for any $t$, at a cost of $t$.
It is clear that $\LD^*\subseteq \LD$. We conjecture that $\LD^*=\LD$. In this
paper, we give several evidences supporting this conjecture. In particular, we
show that it holds for hereditary problems, as well as when the nodes know an
arbitrary upper bound on the total number of nodes. Moreover, we prove that the
conjecture holds in the context of non-deterministic local decision, where
nodes are given certificates (independent of the identities, if they exist),
and the decision consists in verifying these certificates. In short, we prove
that $\NLD^*=\NLD$.

Distributed, Parallel, and Cluster Computing