Investigating the Cost of Anonymity on Dynamic Networks

In this paper we study the difficulty of counting nodes in a synchronous dynamic network where nodes share the same identifier, they communicate by using a broadcast with unlimited bandwidth and, at each synchronous round, network topology may change. To count in such setting, it has been shown that the presence of a leader is necessary. We focus on a particularly interesting subset of dynamic networks, namely $\mathit{\text{Persistent}}\mathit{\text{Distance}}$ - ${\cal G}($PD$){h}$, in which each node has a fixed distance from the leader across rounds and such distance is at most $h$. In these networks the dynamic diameter $D$ is at most $2h$. We prove the number of rounds for counting in ${\cal G}($PD$){2}$isatleastlogarithmicwithrespecttothenetworksize$|V|$. Thanks to this result, we show that counting on any dynamic anonymous network with $D$ constant w.r.t. $\mathrm{\mid }V\mathrm{\mid }$ takes at least $D+\mathrm{\Omega }(\text{log}\mathrm{\mid }V\mathrm{\mid })$ rounds where $\mathrm{\Omega }(\text{log}\mathrm{\mid }V\mathrm{\mid })$ represents the additional cost to be payed for handling anonymity. At the best of our knowledge this is the fist non trivial, i.e. different from $\mathrm{\Omega }(D)$, lower bounds on counting in anonymous interval connected networks with broadcast and unlimited bandwith.