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:
TitleConscious and Unconscious Counting on Anonymous Dynamic Networks
Bibtex cite IDRACTI-RU1-2014-1
Year published 2014
Keywords Anonymous Networks,Dynamic Networks,Counting Algorithms,Dy- namic Graph Adversary
This paper addresses the problem of counting the size of a network where (i) processes have the same identifiers (anonymous nodes) and (ii) the et- work topology constantly changes (dynamic network). Changes are riven by a powerful adversary that can look at internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. The paper proposes two leader-based counting algorithms. Such algorithms are based on a technique that mimics an energy-transfer between network nodes. The first algorithm assumes that the adversary cannot generate either disconnected network graphs or network graphs where nodes have degree greater than D. In such algorithm, the leader can count the size of the network and detect the counting termination in a finite time (i.e., conscious counting algorithm). The second algorithm assumes that the adversary only keeps the network graph connected at any time and we prove that the leader can still converge to a correct count in a finite number of rounds, but it is not conscious when this convergence happens.
Chatzigiannakis, Ioannis
di Luna, G. A
Baldoni, Roberto
Bonomi, Silvia
Conscious and Unconscious Counting on Anonymous Dynamic Networks.pdf (main file)
Publication ID986