Search Results

Documents authored by Gracar, Peter

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.39
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents

Authors: Peter Gracar and Alexandre Stauffer

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
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.
Cite as

Peter Gracar and Alexandre Stauffer. Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gracar_et_al:LIPIcs.APPROX-RANDOM.2018.39,
  author =	{Gracar, Peter and Stauffer, Alexandre},
  title =	{{Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.39},
  URN =		{urn:nbn:de:0030-drops-94439},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.39},
  annote =	{Keywords: Lipschitz surface, spread of information, flooding time, moving agents}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact