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