Metraipolis › archive › dc_2d630f3f025c
Safe Exploration of Arbitrary Dynamic Dangerous Networks — arXiv:2609.19845
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19845
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T03:48:54.684Z
- SHA-256 of the archived text
a49924e90609cfea96c5aa1930e1dbc2b4c69cb862a840a2f5d4f82612896a9a- Stable URL of this page
https://metraipolis.com/documento/dc_2d630f3f025c
How to cite
Safe Exploration of Arbitrary Dynamic Dangerous Networks — arXiv:2609.19845 — arXiv (en), https://arxiv.org/abs/2609.19845 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2d630f3f025c (Metraipolis archive dc_2d630f3f025c, sha256 a49924e90609cfea96c5aa1930e1dbc2b4c69cb862a840a2f5d4f82612896a9a)
BibTeX
@misc{dc2d630f3f025c,
title = {Safe Exploration of Arbitrary Dynamic Dangerous Networks — arXiv:2609.19845},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19845},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2d630f3f025c; sha256 a49924e90609cfea96c5aa1930e1dbc2b4c69cb862a840a2f5d4f82612896a9a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19845. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given a team of agents on the nodes of a graph-based network, the exploration problem requires each node to be visited by at least one agent. In the classical distributed setting of static networks, agents do not know the topology of the network; in the more recently investigated setting of dynamic networks, they may have prior knowledge about the graph class (e.g., trees, tori, rings) or other parameters (e.g., number of nodes). Gotoh et al. (2021) are the first to study the exploration problem of arbitrary dynamic networks, under the necessary minimal assumption that any two nodes will be connected by a temporal path infinitely often (temporal connectivity assumption). In this paper, we extend their study of exploration under temporal connectivity by considering dangerous dynamic networks, i.e., containing possibly one or more black holes. Whenever an agent enters a black hole, it will be trapped forever. The safe exploration problem requires a team to explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. We first prove that, given the necessary (and sufficient) number of agents, a team of oblivious agents can perpetually explore the safe nodes without any prior knowledge of the network or the team, without agent or node IDs, under semi-synchronous schedulers. Then, we provide an algorithm that enables agents to safely explore the network and terminate. In this case, agents are equipped with unique IDs and persistent memory, and they know the number of safe nodes. Yet, in both cases, we prove that it is impossible for a team of agents on dynamic networks to correctly mark only the ports leading to black holes. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DC). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2609.19845 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-10T03:24:19.914Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).