Investigating the Cost of Anonymity on Dynamic Networks

In this paper we study the problem of counting processes in a synchronous dynamic network where a distinguished leader is available and other nodes share the same identifier. The network topology may change at each synchronous round and each node communicates with its neighbors by broadcasting messages. In such networks it is well known that counting requires ω(D) rounds where D is the network diameter. We identify a non-trivial subset of dynamic net- works where counting requires ω (log /V /) rounds even when the dynamic diameter, D, is constant with respect to the network size and the bandwidth is unlimited.