Search Results

Perpetual exploration stands as a fundamental problem in the domain of distributed mobile agent algorithms, where the objective is to ensure that each node within a graph is visited by at least one agent infinitely often. While this issue has received significant attention, particularly concerning ring topologies, the presence of malicious nodes, referred to as black holes, adds more complexity. A black hole can destroy any incoming agent without leaving any trace of its existence. In [Bampas et al., 2015; Královič and Miklík, 2010], the authors have considered this problem in the context of periodic data retrieval. They introduced a variant of a black hole called gray hole (where the adversary chooses whether to destroy an agent or let it pass) among other variants, and showed that 4 asynchronous and co-located agents are necessary and sufficient to solve the periodic data retrieval problem (hence perpetual exploration) in the presence of such a gray hole if each of the nodes of the ring has a whiteboard. This paper investigates the exploration of a ring by introducing a realistic variant of a gray hole, called a "Byzantine black hole". In addition to the usual capabilities of a gray hole, the adversary can also choose whether to erase any previously stored information on that node. Note that in [Bampas et al., 2015; Královič and Miklík, 2010], this problem was considered with only one particular initial scenario (i.e., agents are initially co-located) and one specific communication model (i.e., whiteboard). Now, there can be many other initial scenarios where all agents might not be co-located (i.e., they may be scattered). Also, there are many weaker communications models such as Face-to-Face and Pebble, where this perpetual exploration problem is yet to be investigated in the presence of a Byzantine black hole. The main results of our paper focus on minimizing the number of agents while guaranteeing that they perform the perpetual exploration on a ring even in the presence of a Byzantine black hole under different communication models and for different starting scenarios. On the positive side, as a byproduct of our work, we achieved a better upper and lower bound result (i.e., 3 agents) for perpetual exploration in the presence of a Byzantine black hole (which is a more generalized version of a gray hole), by trading-off the scheduler capability, when the agents are initially co-located, and each node contains a whiteboard.