research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleBrief Announcement: Naming and Counting in Anonymous Unknown Dynamic Networks
Bibtex cite IDRACTI-RU1-2012-25
Booktitle 26th international conference on Distributed Computing (DISC)
Series Lecture Notes in Computer Science
Year published 2012
Volume 7611
Pages 437-438
Publisher Springer-Verlag Berlin Heidelberg
Location Salvador, Brazil
DOI 10.1007/978-3-642-33651-5_46
We study the fundamental naming and counting problems in networks that are anonymous, unknown, and possibly dynamic. Network dynamicity is modeled by the 1-interval connectivity model [KLO10]. We first prove that on static networks with broadcast counting is impossible to solve without a leader and that naming is impossible to solve even with a leader and even if nodes know n. These impossibilities carry over to dynamic networks as well. With a leader we solve counting in linear time. Then we focus on dynamic networks with broadcast. We show that if nodes know an upper bound on the maximum degree that will ever appear then they can obtain an upper bound on n. Finally, we replace broadcast with one-to-each, in which a node may send a different message to each of its neighbors. This variation is then proved to be computationally equivalent to a full-knowledge model with unique names.
Michail, Othon
Chatzigiannakis, Ioannis
Spirakis, Paul
Publication ID974