  In this work, we study the fundamental naming and counting problems (and some
variations) in networks that are anonymous, unknown, and possibly dynamic. In
counting, nodes must determine the size of the network n and in naming they
must end up with unique identities. By anonymous we mean that all nodes begin
from identical states apart possibly from a unique leader node and by unknown
that nodes have no a priori knowledge of the network (apart from some minimal
knowledge when necessary) including ignorance of n. Network dynamicity is
modeled by the 1-interval connectivity model, in which communication is
synchronous and a worst-case adversary chooses the edges of every round subject
to the condition that each instance is connected. We first focus on static
networks with broadcast where we prove that, without a leader, counting is
impossible to solve and that naming is impossible to solve even with a leader
and even if nodes know n. These impossibilities carry over to dynamic networks
as well. We also show that a unique leader suffices in order to solve counting
in linear time. Then we focus on dynamic networks with broadcast. We conjecture
that dynamicity renders nontrivial computation impossible. In view of this, we
let the nodes know an upper bound on the maximum degree that will ever appear
and show that in this case the nodes can obtain an upper bound on n. Finally,
we replace broadcast with one-to-each, in which a node may send a different
message to each of its neighbors. Interestingly, this natural variation is
proved to be computationally equivalent to a full-knowledge model, in which
unique names exist and the size of the network is known.
