License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.39
URN: urn:nbn:de:0030-drops-94439
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9443/
Go to the corresponding LIPIcs Volume Portal

Gracar, Peter ; Stauffer, Alexandre

Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents

pdf-format:
LIPIcs-APPROX-RANDOM-2018-39.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{gracar_et_al:LIPIcs:2018:9443,
  author =	{Peter Gracar and Alexandre Stauffer},
  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 =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9443},
  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}
}

Keywords: Lipschitz surface, spread of information, flooding time, moving agents
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI