2026-07-22T06:37:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9443 2024-03-06T10:44:24Z ddc:004 open_access

Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents Gracar, Peter Stauffer, Alexandre Lipschitz surface spread of information flooding time moving agents We consider the problem of spread of information among mobile agents on the torus. The agents are initially distributed as a Poisson point process on the torus, and move as independent simple random walks. Two agents can share information whenever they are at the same vertex of the torus. We study the so-called flooding time: the amount of time it takes for information to be known by all agents. We establish a tight upper bound on the flooding time, and introduce a technique which we believe can be applicable to analyze other processes involving mobile agents. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Gracar and Alexandre Stauffer 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.39 urn:nbn:de:0030-drops-94439 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.39 eng https://creativecommons.org/licenses/by/3.0/legalcode