📖
Tight Bounds for Black Hole Search with Scattered Agents in Synchronous Rings
Jérémie Chalopin, Shantanu Das, Arnaud Labourel, Euripides Markou

Tight Bounds for Black Hole Search with Scattered Agents in Synchronous Rings

Science & Mathematics Published 2011 Verification Pending

Overview & Synopsis

We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying destroys all mobile agents visiting that node without leaving any trace. We consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Tight Bounds for Black Hole Search with Scattered Agents in Synchronous Rings
Author / Organization Jérémie Chalopin, Shantanu Das, Arnaud Labourel, Euripides Markou
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2011
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-222593
Original Source Link Visit Source Page on hal.science »