Perpetual exploration in anonymous synchronous networks with a Byzantine black hole

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, Partha Sarathi Mandal · 2025

Read Perpetual exploration in anonymous synchronous networks with a Byzantine black hole by Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, Partha Sarathi Mandal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07703.txt.

Description

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal study robot exploration with a treacherous node in a 2025 paper. A team of identical mobile agents starts together and must keep exploring an unknown network forever. One fixed node is a Byzantine black hole: on any round it may destroy all visiting agents, or spare them, as an adversary chooses.

That on-off malice breaks strategies built for a hole that always kills. With no knowledge of the network's size, full exploration may be impossible if the graph hangs by one link. The authors define two task variants and seek agent counts and strategies that still guarantee endless exploration.

Catalog record

CREATORAdri Bhattacharya, Pritam Goswami, Evangelos Bampas, Partha Sarathi Mandal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE206 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-07703

Browse the full library · About the Tower of Babel