LIPIcs.APPROX-RANDOM.2018.39.pdf
- Filesize: 1.47 MB
- 17 pages
Document
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-13
File
Document Identifiers
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Probability and statistics
Keywords
- Lipschitz surface
- spread of information
- flooding time
- moving agents
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Martin T. Barlow. Random walks on supercritical percolation clusters. Annals of Probability, 32(4):3024-3084, 2004. URL: http://dx.doi.org/10.1214/009117904000000748.
- Martin T. Barlow and Ben M. Hambly. Parabolic Harnack inequality and local limit theorem for percolation clusters. Electronic Journal of Probability, 14:1-26, 2009. URL: http://dx.doi.org/10.1214/EJP.v14-587.
- Elisabetta Candellero and Augusto Teixeira. Percolation and isoperimetry on transitive graphs. arXiv, 2015. URL: http://arxiv.org/abs/1507.07765.
- Andrea Clementi, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri. Information Spreading in Stationary Markovian Evolving Graphs. IEEE Transactions on Parallel and Distributed Systems, 22(9):1425-1432, 2011. URL: http://dx.doi.org/10.1109/TPDS.2011.33.
- Andrea E. F. Clementi, Francesco Pasquale, and Riccardo Silvestri. MANETS: High mobility can make up for low transmission power. IEEE/ACM Transactions on Networking, 21(2):610-620, 2009. URL: http://dx.doi.org/10.1109/TNET.2012.2204407.
- Peter Gracar and Alexandre Stauffer. Multi-scale Lipschitz percolation of increasing events for Poisson random walks. arXiv, 2017. URL: http://arxiv.org/abs/1702.08748.
- Peter Gracar and Alexandre Stauffer. Random walks in random conductances: decoupling and spread of infection. arXiv, 2017. URL: http://arxiv.org/abs/1701.08021.
- Harry Kesten and Vladas Sidoravicius. The spread of a rumor or infection in a moving population. Annals of Probability, 33(6):2402-2462, 2005. URL: http://dx.doi.org/10.1214/009117905000000413.
- Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, and Yajun Wang. Information Dissemination via Random Walks in d-Dimensional Space. arXiv, 2011. URL: http://arxiv.org/abs/1104.5268.
- T. M. Liggett, R. H. Schonmann, and A. M. Stacey. Domination by product measures. Ann. Probab., 25(1):71-95, 01 1997. URL: http://dx.doi.org/10.1214/aop/1024404279.
- Yuval Peres, Alistair Sinclair, Perla Sousi, and Alexandre Stauffer. Mobile geometric graphs: Detection, coverage and percolation. Probability Theory and Related Fields, 156(1-2):273-305, 2013. URL: http://dx.doi.org/10.1007/s00440-012-0428-1.
- Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci, and Eli Upfal. Tight bounds on information dissemination in sparse mobile networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '11, pages 355-362, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993806.1993882.
- Vladas Sidoravicius and Alain-Sol Sznitman. Percolation for the vacant set of random interlacements. Communications on Pure and Applied Mathematics, 62(6):831-858, 2009. URL: http://dx.doi.org/10.1002/cpa.20267.
- Alexandre Stauffer. Space-time percolation and detection by mobile nodes. Annals of Applied Probability, 25(5):2416-2461, 2015. URL: http://dx.doi.org/10.1214/14-AAP1052.
- Alain-Sol Sznitman. Decoupling inequalities and interlacement percolation on G×ℤ. Inventiones mathematicae, 187(3):645-706, 2012. URL: http://dx.doi.org/10.1007/s00222-011-0340-9.