Milani, Alessia ;
Mosteiro, Miguel A.
A Faster Counting Protocol for Anonymous Dynamic Networks
Abstract
We study the problem of counting the number of nodes in a slottedtime communication network, under the challenging assumption that nodes do not have identifiers and the network topology changes frequently. That is, for each time slot links among nodes can change arbitrarily provided that the network is always connected.
This network model has been motivated by the ongoing development of new communication technologies that enable the deployment of a massive number of devices with highly dynamic connectivity patterns. Tolerating dynamic topologies is clearly crucial in face of mobility and unreliable communication. Current communication networks do have node identifiers though. Nevertheless, in future massive networks, it might be suitable to avoid nodes IDs to facilitate mass production. Consequently, knowing what is the cost of anonymity is of paramount importance to understand what is feasible or not for future generations of Dynamic Networks.
Counting is a fundamental task in distributed computing since knowing the size of the system often facilitates the desing of solutions for more complex problems. Also, the size of the system is usually used to decide termination in distributed algorithms. Currently, the best upper bound proved on the running time to compute the exact network size is doubleexponential. However, 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 paper we make a significant step towards answering this question by presenting a distributed Counting protocol for Anonymous Dynamic Networks which has exponential time complexity. This algorithm, which we call Incremental Counting, ensures that eventually every node knows the exact size of the system and stops executing the protocol. Previous Counting protocols have either doubleexponential time complexity, or they are exponential but do not terminate, or terminate but do not provide runningtime guarantees, or guarantee only an exponential upper bound on the network size. Other protocols are heuristic and do not guarantee the correct count.
BibTeX  Entry
@InProceedings{milani_et_al:LIPIcs:2016:6617,
author = {Alessia Milani and Miguel A. Mosteiro},
title = {{A Faster Counting Protocol for Anonymous Dynamic Networks}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {113},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897989},
ISSN = {18688969},
year = {2016},
volume = {46},
editor = {Emmanuelle Anceaume and Christian Cachin and Maria PotopButucaru},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6617},
URN = {urn:nbn:de:0030drops66179},
doi = {10.4230/LIPIcs.OPODIS.2015.28},
annote = {Keywords: Anonymous Dynamic Networks, Counting, Timevarying Graphs}
}
2016
Keywords: 

Anonymous Dynamic Networks, Counting, Timevarying Graphs 
Seminar: 

19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Issue date: 

2016 
Date of publication: 

2016 