2013 | OriginalPaper | Buchkapitel
Naming and Counting in Anonymous Unknown Dynamic Networks
verfasst von : Othon Michail, Ioannis Chatzigiannakis, Paul G. Spirakis
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.