2013 | OriginalPaper | Chapter
Naming and Counting in Anonymous Unknown Dynamic Networks
Authors : Othon Michail, Ioannis Chatzigiannakis, Paul G. Spirakis
Published in: Stabilization, Safety, and Security of Distributed Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this work, we study the fundamental naming and counting problems (and some variations) in networks that are anonymous, unknown, and possibly dynamic. In
counting
, nodes must determine the size of the network
n
and in
naming
they must end up with unique identities. By
anonymous
we mean that all nodes begin from identical states apart possibly from a unique leader node and by
unknown
that nodes have no a priori knowledge of the network (apart from some minimal knowledge when necessary) including ignorance of
n
. Network dynamicity is modeled by the 1-interval connectivity model [KLO10], in which communication is synchronous and a (worst-case) adversary chooses the edges of every round subject to the condition that each instance is connected. We first focus on static networks with broadcast where we prove that, without a leader, counting is impossible to solve 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. We also show that a unique leader suffices in order to solve counting in linear time. Then we focus on dynamic networks with broadcast. We conjecture that dynamicity renders nontrivial computation impossible. In view of this, we let the nodes know an upper bound on the maximum degree that will ever appear and show that in this case the nodes 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. Interestingly, this natural variation is proved to be computationally equivalent to a full-knowledge model, in which unique names exist and the size of the network is known.