Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Black Hole Search with Tokens in Interconnected Networks
verfasst von : Wei Shi
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the Black Hole search problem using mobile agents in three interconnected network topologies: hypercube, torus and complete network. We do so without relying on local storage. Instead we use a less-demanding and less-expensive
token
mechanism. We demonstrate that the Black Hole can be located with a minimum of two (2)
co-located
agents performing Θ(
n
) moves with
O
(1) tokens, in each of these three topologies. Then we study the Black Hole search problem with
scattered
agents. We show that the optimal number of moves can be achieved with the optimal number of mobile agents using
O
(1) tokens.