Document Open Access Logo

Tight Bounds on Distributed Exploration of Temporal Graphs

Authors Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, Nicola Santoro

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.22.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Tsuyoshi Gotoh
  • Osaka University, Japan
Paola Flocchini
  • University of Ottawa, Canada
Toshimitsu Masuzawa
  • Osaka University, Japan
Nicola Santoro
  • Carleton University, Canada

Acknowledgements

This research was partly supported by NSERC through the Discovery Grant program, by Prof. Flocchini’s University Research Chair, and JSPS KAKENHI Grant Number 19H04085.

Cite As Get BibTex

Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Tight Bounds on Distributed Exploration of Temporal Graphs. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.22

Abstract

Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs.
We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. 
We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed algorithm
  • Mobile agents
  • Exploration of dynamic networks
  • Arbitrary footprint

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Albers and M. Henzinger. Exploring unknown environments. SIAM Journal on Computing, 29(4):1164-1188, 2000. Google Scholar
  2. C. Avin, M. Koucky, and Z. Lotker. How to explore a fast-changing world. In Proc. of the 35th Int. Colloquium on Automata, Languages and Programming (ICALP), pages 121-132, 2008. Google Scholar
  3. E. Bampas, L. Gasieniec, N. Hanusse, D. Ilcinkas, R. Klasing, A. Kosowski, and T. Radzik. Robustness of the rotor-router mechanism. Algorithmica, 78(3):869-895, 2017. Google Scholar
  4. M. Bournat, A.K. Datta, and S. Dubois. Self-stabilizing robots in highly dynamic environments. Theoretical Computer Science, 772:88-110, 2019. Google Scholar
  5. M. Bournat, S. Dubois, and F. Petit. Computability of perpetual exploration in highly dynamic rings. In Proc. IEEE 37th Int. Conference on Distributed Computing Systems (ICDCS), pages 794-804, 2017. Google Scholar
  6. A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. Int. Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  7. J. Chalopin, P. Flocchini, B. Mans, and N. Santoro. Network exploration by silent and oblivious robots. In Proc. of 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG), pages 208-219, 2010. Google Scholar
  8. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg. Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms, 4(4):1-18, 2008. Google Scholar
  9. S. Das. Graph Exploration with Mobile Agents. Chapter 16 of [20], pages 403-422, 2019. Google Scholar
  10. X. Deng and C. H. Papadimitriou. Exploring an unknown graph. Journal of Graph Theory, 32(3):265-297, 1999. Google Scholar
  11. G.A. Di Luna. Mobile Agents on Dynamic Graphs. Chapter 20 of [20], pages 549-584, 2019. Google Scholar
  12. G.A. Di Luna, S. Dobrev, P. Flocchini, and N. Santoro. Live exploration of dynamic rings. In Proc. IEEE 36th International Conference on Distributed Computing Systems (ICDCS), pages 570-579, 2016. Google Scholar
  13. Y. Dieudonné and A. Pelc. Deterministic network exploration by anonymous silent agents with local traffic reports. ACM Transactions on Algorithms, 11(2):Article No. 10, 2014. Google Scholar
  14. S. Dobrev, L. Narayanan, J. Opatrny, and D. Pankratov. Exploration of high-dimensional grids by finite automata. In Proc. 46th Int. Colloquium on Automata, Languages, and Programming (ICALP), pages 1-16, 2019. Google Scholar
  15. T. Erlebach, M. Hoffmann, and F. Kammer. On temporal graph exploration. In Proc. of 42th International Colloquium on Automata, Languages, and Programming (ICALP), pages 444-455, 2015. Google Scholar
  16. T. Erlebach and J. T. Spooner. Faster exploration of degree-bounded temporal graphs. In Proc. of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 1-13, 2018. Google Scholar
  17. A. Ferreira. Building a reference combinatorial model for MANETs. IEEE Network, 18(5):24-29, 2004. Google Scholar
  18. P. Flocchini, M. Kellett, P. Mason, and N. Santoro. Searching for black holes in subways. Theory of Computing Systems, 50(1):158-184, 2012. Google Scholar
  19. P. Flocchini, B. Mans, and N. Santoro. On the exploration of time-varying networks. Theoretical Computer Science, 469:53-68, 2013. Google Scholar
  20. P. Flocchini, G. Prencipe, and N. Santoro (Eds). Distributed Computing by Mobile Entities. Springer, 2019. Google Scholar
  21. P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg. Graph exploration by a finite automaton. Theoretical Computer Science, 345(2-3):331-344, 2005. Google Scholar
  22. P. Fraigniaud, D. Ilcinkas, and A. Pelc. Impact of memory size on graph exploration capability. Discrete Applied Mathematics, 156(12):2310-2319, 2008. Google Scholar
  23. T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa. Group Exploration of Dynamic Tori. In Proc. IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pages 775-785, 2018. Google Scholar
  24. B. Haeupler and F. Kuhn. Lower bounds on information dissemination in dynamic networks. In Proc. 26th International Symposium on Distributed Computing (DISC), pages 166-180, 2012. Google Scholar
  25. F. Harary and G. Gupta. Dynamic graph models. Mathematical and Computer Modelling, 25(7):79-88, 1997. Google Scholar
  26. D. Ilcinkas, R. Klasing, and A.M. Wade. Exploration of constantly connected dynamic graphs based on cactuses. In Proc. 21st International Colloquium Structural Information and Communication Complexity (SIROCCO), pages 250-262, 2014. Google Scholar
  27. D. Ilcinkas and A.M. Wade. On the power of waiting when exploring public transportation systems. In Proc. 15th International Conference on Principles of Distributed Systems (OPODIS), pages 451-464, 2011. Google Scholar
  28. D. Ilcinkas and A.M. Wade. Exploration of the T-Interval-connected dynamic graphs: the case of the ring. Theory Computing Systems, 62(4):1144-1160, 2018. Google Scholar
  29. A. Kosowski and D. Pajak. Does adding more agents make a difference? A case study of cover time for the rotor-router. J. Comput. Syst. Sci., 106:80-93, 2019. Google Scholar
  30. F. Kuhn, N. A. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proc. 42nd ACM Symposium on Theory of Computing (STOC), pages 513-522, 2010. Google Scholar
  31. F. Kuhn and R. Oshman. Coordinated consensus in dynamic networks. In Proc. 30th Symposium on Principles of Distributed Computing (PODC), pages 1-10, 2011. Google Scholar
  32. O. Michail and P. Spirakis. Traveling Salesman Problems in Temporal Graphs. Theoretical Computer Science, 634:1-23, 2016. Google Scholar
  33. P. Panaite and A. Pelc. Exploring unknown undirected graphs. Journal of Algorithms, 33:281-295, 1999. Google Scholar
  34. C. Shannon. Presentation of a maze-solving machine. In Proc. of the 8th Conf. of the Josiah Macy Jr. Foundation (Cybernetics), pages 173-180, 1951. Google Scholar
  35. V. Yanovsky, A. Bruckstein, and I. Wagner. A distributed ant algorithm for efficently patrolling a network. Algorithmica, 37(3):165-186, 2003. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact