Scholarlink

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 assumed in some of the previous works. Our focus is on ring networks using synchronous agents. We provide two solutions: a 4-agent algorithm for rings without the knowledge of n but when only a single link leading to the black hole is found and a 3-agent algorithm assuming known ring size. We also prove that the problem is not solvable with 2-agents (even with whiteboard and a home base that remains safe), making our 3-agent algorithm optimal.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Brief Announcement: Searching for an Eventually-Emerging Black Hole in Rings

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • François Bonnet,
  • Quentin Bramas,
  • Anissa Lamani

摘要

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 assumed in some of the previous works. Our focus is on ring networks using synchronous agents. We provide two solutions: a 4-agent algorithm for rings without the knowledge of n but when only a single link leading to the black hole is found and a 3-agent algorithm assuming known ring size. We also prove that the problem is not solvable with 2-agents (even with whiteboard and a home base that remains safe), making our 3-agent algorithm optimal.