DROPS

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

Black Hole Search in Dynamic Tori

Abstract

Cite as