  Counting the number of nodes in Anonymous Dynamic Networks is enticing from
an algorithmic perspective: an important computation in a restricted platform
with promising applications. Starting with Michail, Chatzigiannakis, and
Spirakis [19], a flurry of papers sped up the running time guarantees from
doubly-exponential to polynomial [16]. There is a common theme across all those
works: a distinguished node is assumed to be present, because Counting cannot
be solved deterministically without at least one. In the present work we study
challenging questions that naturally follow: how to efficiently count with more
than one distinguished node, or how to count without any distinguished node.
More importantly, what is the minimal information needed about these
distinguished nodes and what is the best we can aim for (count precision,
stochastic guarantees, etc.) without any. We present negative and positive
results to answer these questions. To the best of our knowledge, this is the
first work that addresses them.
