View article

We study the problem of Counting the number of nodes in Anonymous Dynamic Network: nodes do not have identifiers and the network topology changes frequently. Counting is a fundamental task in distributed computing, for instance, to decide termination. Knowing what is the cost of anonymity is of paramount importance to understand what is feasible for future generations of Dynamic Networks, where the lack of nodes identifiers might facilitate mass production. Previous upper bounds to compute the exact network size are double-exponential. Strikingly, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this work, we achieve an exponential speedup presenting Incremental Counting (IC), a distributed Counting protocol for Anonymous Dynamic Networks that has exponential time complexity …