|Type of publication:||Inproceedings|
|Title||Conscious and Unconscious Counting on Anonymous Dynamic Networks|
|Bibtex cite ID||RACTI-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.
Conscious and Unconscious Counting on Anonymous Dynamic Networks.pdf (main file) |