  Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring,
leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed
algorithm that can start from any initial configuration of the network (i.e.,
every node has an arbitrary value assigned to each of its variables), and
eventually converge to a configuration satisfying $\Pi$. It is known that
leader election does not have a deterministic self-stabilizing algorithm using
a constant-size register at each node, i.e., for some networks, some of their
nodes must have registers whose sizes grow with the size $n$ of the networks.
On the other hand, it is also known that leader election can be solved by a
deterministic self-stabilizing algorithm using registers of $O(\log \log n)$
bits per node in any $n$-node bounded-degree network. We show that this latter
space complexity is optimal. Specifically, we prove that every deterministic
self-stabilizing algorithm solving leader election must use $\Omega(\log \log
n)$-bit per node registers in some $n$-node networks. In addition, we show that
our lower bounds go beyond leader election, and apply to all problems that
cannot be solved by anonymous algorithms.
