2026-09-08T01:21:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26252 2026-09-05T19:39:24Z ddc:004 open_access

Searching for an Eventually-Emerging Black Hole in Rings Bonnet, François Bramas, Quentin Lamani, Anissa Black hole search mobile agent distributed computing We study a novel variant of the Black Hole Search (BHS) problem where the black hole, a node that silently destroys visiting agents, can appear at any time during execution, rather than being present initially, as is assumed in all previous work. Our focus is on ring networks, and we examine this variant of the BHS problem under various assumptions, including whether the ring size is known and whether agents can use pebbles for marking nodes. For synchronous agents, we provide four solutions: (1) a 4-agent algorithm for rings without additional assumptions, (2) a 3-agent algorithm assuming known ring size, (3) a 3-agent algorithm using pebbles, and (4) a 3-agent solution without additional assumptions but having a quadratic time complexity. For asynchronous agents, we develop two algorithms: one using n agents without additional assumptions, and another using only 4 agents with pebbles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik François Bonnet and Quentin Bramas and Anissa Lamani 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.18 urn:nbn:de:0030-drops-262527 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode