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

Peter Gracar; Alexandre Stauffer

doi:10.4230/LIPIcs.APPROX-RANDOM.2018.39

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

Peter Gracar, Alexandre Stauffer

University of Cologne

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

1 Citation (SciVal)

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 language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
Place of Publication	Leibniz, Germany
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)	9783959770859
DOIs	https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39
Publication status	Published - 1 Aug 2018
Event	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 Duration: 20 Aug 2018 → 22 Aug 2018

Publication series

Name	Leibniz International Proceedings in Informatics
Volume	116

Conference

Conference	21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
Country/Territory	USA United States
City	Princeton
Period	20/08/18 → 22/08/18

Keywords

Flooding Time
Lipschitz Surface
Moving Agents
Spread Of Information

ASJC Scopus subject areas

Software

Access to Document

10.4230/LIPIcs.APPROX-RANDOM.2018.39Licence: CC BY

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 Article 39 (Leibniz International Proceedings in Informatics; Vol. 116). 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 or section in a book/report/conference proceeding › Chapter in a published conference proceeding

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). doi: 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 = aug,

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",

note = "21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 ; Conference date: 20-08-2018 Through 22-08-2018",

}

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 - Chapter in a published conference proceeding

AN - SCOPUS:85052475313

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

T2 - 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018

Y2 - 20 August 2018 through 22 August 2018

ER -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Early Career Fellowship - Mathematical Analysis of Strongly Correlated Processes on Discrete Dynamic Structures

Cite this

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

Early Career Fellowship - Mathematical Analysis of Strongly Correlated Processes on Discrete Dynamic Structures

Cite this