10.1007/978-3-642-45346-5_3
Abshoff, Sebastian
Sebastian
Abshoff
Benter, Markus
Markus
Benter
Cord-Landwehr, Andreas
Andreas
Cord-Landwehr
Malatyali, Manuel
Manuel
Malatyali
Meyer auf der Heide, Friedhelm
Friedhelm
Meyer auf der Heide
Token Dissemination in Geometric Dynamic Networks
2013
2017-10-17T12:42:25Z
2019-01-03T13:16:13Z
conference
https://ris.uni-paderborn.de/record/477
https://ris.uni-paderborn.de/record/477.json
193169 bytes
application/pdf
We consider the k-token dissemination problem, where k initially arbitrarily distributed tokens have to be disseminated to all nodes in a dynamic network (as introduced by Kuhn et al., STOC 2010). In contrast to general dynamic networks, our dynamic networks are unit disk graphs, i.e., nodes are embedded into the Euclidean plane and two nodes are connected if and only if their distance is at most R. Our worst-case adversary is allowed to move the nodes on the plane, but the maximum velocity v_max of each node is limited and the graph must be connected in each round. For this model, we provide almost tight lower and upper bounds for k-token dissemination if nodes are restricted to send only one token per round. It turns out that the maximum velocity v_max is a meaningful parameter to characterize dynamics in our model.