Document Open Access Logo

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

Authors Peter Gracar, Alexandre Stauffer

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2018.39.pdf
  • Filesize: 1.47 MB
  • 17 pages

Document Identifiers

Related Versions

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Peter Gracar
  • Mathematical Institute, University of Cologne, Weyertal 86-90, 50931 Köln, Germany
Alexandre Stauffer
  • Department of Mathematical Sciences, University of Bath, Claverton Down, Bath, BA2 7AY, United Kingdom

Funding

  • Stauffer, Alexandre: Supported by a Marie Curie Career Integration Grant PCIG13-GA-2013-618588 DSRELIS, and an EPSRC Early Career Fellowship.

References

  1. 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.
  2. 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.
  3. Elisabetta Candellero and Augusto Teixeira. Percolation and isoperimetry on transitive graphs. arXiv, 2015. URL: http://arxiv.org/abs/1507.07765.
  4. 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.
  5. 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.
  6. 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.
  7. Peter Gracar and Alexandre Stauffer. Random walks in random conductances: decoupling and spread of infection. arXiv, 2017. URL: http://arxiv.org/abs/1701.08021.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact