Mobile Agents in Adversarial Networks: Perpetual Exploration in Presence of Malicious Host
Time: 14:00 -- Location: bat 650, 445
summary: Perpetual exploration is a central problem in distributed computing, requiring a team of mobile agents to repeatedly visit every node of a network indefinitely. While the problem is well understood in benign environments, its complexity increases dramatically in the presence of adversarial nodes. A particularly challenging scenario arises even with an adversary called a grey hole, i.e., a malicious node that can choose specific rounds in which it destroys any agent incoming or already on it, making reliable exploration fundamentally difficult.
In this talk, we introduce and study a stronger adversarial model, termed the Byzantine black hole. This model extends the classical grey hole by not only allowing the adversary to eliminate agents but also to erase any information stored at the compromised node during adversarially chosen rounds. This added capability significantly impacts both the design and feasibility of exploration protocols.
We begin by investigating the problem on ring networks, analyzing how key factors, such as initial agent placement (co-located vs. scattered) and communication mechanisms (face-to-face interaction, movable tokens, or whiteboards), influence solvability of the problem. For these settings, we establish several tight bounds on the minimum number of agents required for perpetual exploration.
We then extend our results to general networks. For tree topologies, we derive tight bounds on the agent complexity. For arbitrary graphs, we present an exploration algorithm that operates with 2Δ+4 agents, where Δ denotes the maximum degree of the network, and complement this with a lower bound of 2Δ−1 agents under co-located initial configuration and face-to-face communication.
Overall, this talk will highlight the intricate interplay between adversarial power, communication models, and network structure, advancing our understanding of resilient mobile-agent systems in hostile environments.
The results presented in this talk are based on joint works with Prof. Partha Sarathi Mandal, Dr. Evangelos Bampas, Adri Bhattacharya, and Raja Das [1,2].
References:
[1] Perpetual Exploration of a Ring in Presence of Byzantine Black Hole. Pritam Goswami, Adri Bhattacharya, Raja Das and Partha Sarathi Mandal. 28th International Conference on Principles of Distributed Systems, OPODIS 2024, Lucca, Italy, December 11-13, 2024. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2024.17
[2] Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. Adri Bhattacharya, Pritam Goswami, Evangelos Bampas and Partha Sarathi Mandal. 39th International Symposium on Distributed Computing, DISC 2025. Berlin, Germany, October 27-31, 2025. URL: https://doi.org/10.4230/LIPIcs.DISC.2025.16