文章基本信息

标题：Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents
本地全文：下载
作者：Peter Gracar ; Alexandre Stauffer
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：116
页码：1-17
DOI：10.4230/LIPIcs.APPROX-RANDOM.2018.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Lipschitz surface; spread of information; flooding time; moving agents