DROPS

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 Bhattacharya, Adri

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