Paper Info
Title
A Faster Exact-Counting Protocol for Anonymous Dynamic Networks.
Abstract
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 and computes the exact size of the system. We complement the theoretical study evaluating IC experimentally. We tested a variety of network topologies that may appear in practice, including extremal cases such as trees, paths, and continuously changing topologies. Our simulations showed that IC is polynomial for all the inputs tested, paving the way to use it in practical applications where the network topology is predictable.
Year
DOI
Venue
2018
10.1007/s00453-017-0367-4
Algorithmica
Keywords
Field
DocType
Anonymous dynamic networks,Counting,Distributed algorithms,Time-varying graphs
Dynamic network analysis,Discrete mathematics,Exponential function,Polynomial,Identifier,Network topology,Theoretical computer science,Distributed algorithm,Anonymity,Mathematics,Speedup
Journal
Volume
Issue
ISSN
80
11
0178-4617
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
Maitri Chakraborty110.70
Alessia Milani218715.54
Miguel A. Mosteiro319624.31