Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents

Peter Gracar, Alexandre Stauffer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
Place of PublicationLeibniz, Germany
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770859
DOIs
Publication statusPublished - 1 Aug 2018
Event21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 - Princeton, USA United States
Duration: 20 Aug 201822 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics
Volume116

Conference

Conference21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
CountryUSA United States
CityPrinceton
Period20/08/1822/08/18

Fingerprint

Mobile agents

Keywords

  • Flooding Time
  • Lipschitz Surface
  • Moving Agents
  • Spread Of Information

ASJC Scopus subject areas

  • Software

Cite this

Gracar, P., & Stauffer, A. (2018). Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018 [39] (Leibniz International Proceedings in Informatics; Vol. 116). Leibniz, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39

Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents. / Gracar, Peter; Stauffer, Alexandre.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Leibniz, Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 39 (Leibniz International Proceedings in Informatics; Vol. 116).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Gracar, P & Stauffer, A 2018, Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents. in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018., 39, Leibniz International Proceedings in Informatics, vol. 116, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz, Germany, 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018, Princeton, USA United States, 20/08/18. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39
Gracar P, Stauffer A. Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Leibniz, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. 39. (Leibniz International Proceedings in Informatics). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39
Gracar, Peter ; Stauffer, Alexandre. / Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Leibniz, Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. (Leibniz International Proceedings in Informatics).
@inproceedings{991c2b6fd56141bda54b8de54ca14d47,
title = "Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents",
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.",
keywords = "Flooding Time, Lipschitz Surface, Moving Agents, Spread Of Information",
author = "Peter Gracar and Alexandre Stauffer",
year = "2018",
month = "8",
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2018.39",
language = "English",
isbn = "9783959770859",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018",
address = "Germany",

}

TY - GEN

T1 - Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents

AU - Gracar, Peter

AU - Stauffer, Alexandre

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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.

AB - 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.

KW - Flooding Time

KW - Lipschitz Surface

KW - Moving Agents

KW - Spread Of Information

UR - http://www.scopus.com/inward/record.url?scp=85052475313&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2018.39

DO - 10.4230/LIPIcs.APPROX-RANDOM.2018.39

M3 - Conference contribution

SN - 9783959770859

T3 - Leibniz International Proceedings in Informatics

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

CY - Leibniz, Germany

ER -