Black Hole Search in Dynamic Tori

التفاصيل البيبلوغرافية
العنوان: Black Hole Search in Dynamic Tori
المؤلفون: Bhattacharya, Adri, Italiano, Giuseppe F., Mandal, Partha Sarathi
سنة النشر: 2024
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Distributed, Parallel, and Cluster Computing
الوصف: We investigate the black hole search problem by a set of mobile agents in a dynamic torus. Black hole is defined to be a dangerous stationary node which has the capability to destroy any number of incoming agents without leaving any trace of its existence. A torus of size $n\times m$ ($3\leq n \leq 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 \textit{time}) for termination. We consider two initial configurations of mobile agents: first, the agents are co-located and 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.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2402.04746
رقم الأكسشن: edsarx.2402.04746
قاعدة البيانات: arXiv