Titre du sujet: Black Hole Search in Graphs
Encadrant: Ralf Klasing, André Raspaud
Laboratoire et équipe de recherche: Combinatoire et Algorithmique
Description
détaillée:
Problems
related to security in a network environment have attracted
many
researchers. For instance protecting a host, i.e., a node of a
network,
from an agent's attack as well as protecting mobile agents
from
"host attacks", i.e., harmful items stored in nodes of the network,
are
important with respect to security of a network environment.
Various
methods of protecting mobile agents against malicious hosts
have been
discussed in the literature.
We consider
here malicious hosts of a particularly harmful nature,
called "black holes". A black hole is a stationary process residing
in a node of a network and destroying all mobile agents visiting the
node, without leaving any trace. We are dealing with the issue of
locating a black hole: assuming that there is at most one black hole
in the network, at least one surviving agent must find the location
of the black hole if it exists, or answer that there is no black hole,
otherwise. The only way to locate the black hole is to visit it by at
least one agent, hence, at least two agents are necessary for one of
them to locate the black hole and survive. We assume that the number
of agents is the minimum possible for our task, i.e., 2, and that
they start from the same node, known to be safe.
The issue of efficient black hole search was extensively studied in
the literature in many types of networks under the scenario of a
totally asynchronous network (i.e., no upper bound on this time
needed for an edge traversal). In this setting it was observed that,
in order to solve the problem, the network must be 2-connected.
Moreover, it is impossible to answer the question of whether a
black hole actually exists in an asynchronous network, hence many
papers work under the assumption that there is exactly one black
hole and the task is to locate it.
Here, we consider networks that are partially synchronous, i.e. there is
an upper bound on the time needed by an agent for traversing any edge.
This assumption makes a dramatic change to the problem: the black hole
can be located by two agents in any graph; moreover the agents can
decide if there is a black hole or not in the network. If, without loss
of generality, we normalize to 1 the upper bound on edge traversal time,
then we can define the cost of a Black Hole Search as the time taken
under the worst-case location of the black hole (or when it does not
exist in the network), assuming that all the edge traversals take time 1.
References:
==========
[1] R. Klasing, E. Markou, T. Radzik, and F. Sarracco.
Approximation bounds for Black Hole Search problems.
In Proceedings of the 9th International Conference on
Principles of Distributed Systems (OPODIS 2005), Lecture
Notes in Computer Science, December 2005. Springer Verlag.
[2] R. Klasing, E. Markou, T. Radzik, and F. Sarracco.
Hardness and approximation results for black hole search
in arbitrary graphs. In Proceedings of the 12th Colloquium
on Structural Information and Communication Complexity (SIROCCO 2005),
volume 3499 of Lecture Notes in Computer Science, pages 200--215, May 2005.
Springer Verlag.
http://www-sop.inria.fr/mascotte/Publications/?lang=fr&to_inc=Author/KLASING-R.html