Abshoff, Sebastian; Benter, Markus; Cord-Landwehr, Andreas; Malatyali, Manuel; Meyer auf der Heide, Friedhelm Token dissemination in geometric dynamic networks. (English) Zbl 1397.68013 Flocchini, Paola (ed.) et al., Algorithms for sensor systems. 9th international symposium on algorithms and experiments for sensor systems, wireless networks and distributed robotics, ALGOSENSORS 2013, Sophia Antipolis, France, September 5–6, 2013. Revised selected papers. Berlin: Springer (ISBN 978-3-642-45345-8/pbk; 978-3-642-45346-5/ebook). Lecture Notes in Computer Science 8243, 22-34 (2014). Summary: 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 F. Kuhn et al. [in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. New York, NY: Association for Computing Machinery (ACM). 513–522 (2010; Zbl 1293.68305)]). 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.For the entire collection see [Zbl 1327.68019]. Cited in 3 Documents MSC: 68M14 Distributed systems 68R10 Graph theory (including graph drawing) in computer science Keywords:geometric dynamic networks; token dissemination; distributed computing Citations:Zbl 1293.68305 PDFBibTeX XMLCite \textit{S. Abshoff} et al., Lect. Notes Comput. Sci. 8243, 22--34 (2014; Zbl 1397.68013) Full Text: DOI