DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2025.16

Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

Authors: Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

In this paper, we investigate the following question: "How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves maliciously, under the control of an adversary?" This malicious node is termed as "Byzantine black hole (BBH)" and at any given round it may choose to destroy all visiting agents, or none of them. While investigating this question, we found out that this subtle power turns out to drastically undermine even basic exploration strategies which have been proposed in the context of a classical, always active, black hole. We study this perpetual exploration problem in the presence of at most one BBH, without initial knowledge of the network size. Since the underlying graph may be 1-connected, perpetual exploration of the entire graph may be infeasible. Accordingly, we define two variants of the problem, termed as PerpExploration-BBH and PerpExploration-BBH-Home. In the former, the agents are tasked to perform perpetual exploration of at least one component, obtained after the exclusion of the BBH. In the latter, the agents are tasked to perform perpetual exploration of the component which contains the home node, where agents are initially co-located. Naturally, PerpExploration-BBH-Home is a special case of PerpExploration-BBH. The mobile agents are controlled by a synchronous scheduler, and they communicate via face-to-face model of communication. The main objective in this paper is to determine the minimum number of agents necessary and sufficient to solve these problems. We first consider the problems in acyclic networks, and we obtain optimal algorithms that solve PerpExploration-BBH with 4 agents, and PerpExploration-BBH-Home with 6 agents in trees. The lower bounds hold even in path graphs. In general graphs, we give a non-trivial lower bound of 2Δ-1 agents for PerpExploration-BBH, and an upper bound of 3Δ+3 agents for PerpExploration-BBH-Home. To the best of our knowledge, this is the first paper that studies a variant of a black hole in arbitrary networks, without initial topological knowledge about the network.

Cite as

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal. Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.DISC.2025.16,
  author =	{Bhattacharya, Adri and Goswami, Pritam and Bampas, Evangelos and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.16},
  URN =		{urn:nbn:de:0030-drops-248333},
  doi =		{10.4230/LIPIcs.DISC.2025.16},
  annote =	{Keywords: mobile agents, perpetual exploration, malicious host, Byzantine black hole}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2024.17

Perpetual Exploration of a Ring in Presence of Byzantine Black Hole

Authors: Pritam Goswami, Adri Bhattacharya, Raja Das, and Partha Sarathi Mandal

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract

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.

Cite as

Pritam Goswami, Adri Bhattacharya, Raja Das, and Partha Sarathi Mandal. Perpetual Exploration of a Ring in Presence of Byzantine Black Hole. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goswami_et_al:LIPIcs.OPODIS.2024.17,
  author =	{Goswami, Pritam and Bhattacharya, Adri and Das, Raja and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration of a Ring in Presence of Byzantine Black Hole}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.17},
  URN =		{urn:nbn:de:0030-drops-225532},
  doi =		{10.4230/LIPIcs.OPODIS.2024.17},
  annote =	{Keywords: Mobile Agents, Exploration, Ring, Black Hole, Malicious host, Byzantine Fault}
}

Document

DOI: 10.4230/LIPIcs.SAND.2024.6

Black Hole Search in Dynamic Tori

Authors: Adri Bhattacharya, Giuseppe F. Italiano, and Partha Sarathi Mandal

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

We investigate the black hole search problem using a set of mobile agents in a dynamic torus. A black hole is defined as a dangerous stationary node that has the capability to destroy any number of incoming agents without leaving any trace of its existence. A torus of size n× m (3 ≤ n ≤ m) is a collection of n row rings and m column rings, and the dynamicity is such that each ring is considered to be 1-interval connected, i.e., in other words at most one edge can be missing from each ring at any round. The parameters which define the efficiency of any black hole search algorithm are: the number of agents and the number of rounds (or time) for termination. We consider two initial configurations of mobile agents: first, the agents are co-located, second, the agents are scattered. In each case, we establish lower and upper bounds on the number of agents and on the amount of time required to solve the black hole search problem.

Cite as

Adri Bhattacharya, Giuseppe F. Italiano, and Partha Sarathi Mandal. Black Hole Search in Dynamic Tori. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.SAND.2024.6,
  author =	{Bhattacharya, Adri and Italiano, Giuseppe F. and Mandal, Partha Sarathi},
  title =	{{Black Hole Search in Dynamic Tori}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.6},
  URN =		{urn:nbn:de:0030-drops-198840},
  doi =		{10.4230/LIPIcs.SAND.2024.6},
  annote =	{Keywords: Black Hole Search, Time Varying Graphs, Dynamic Torus, Distributed Algorithms, Mobile Agents}
}

Search Results

Documents authored by Mandal, Partha Sarathi

Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

Abstract

Cite as

Perpetual Exploration of a Ring in Presence of Byzantine Black Hole

Abstract

Cite as

Black Hole Search in Dynamic Tori

Abstract

Cite as

Thanks for your feedback!

Could not send message