Identifying Hostile Nodes in Networks Using Mobile Agents
Ευριπίδης Μάρκου · Bulletin of the European Association for Theoretical Computer Science · 2012
In distributed mobile computing environments one of the most pressing concerns is security. Two are the most important security threats: a malicious mobile process which can move along the network and a stationary harmful process which resides at a host. One of the most studied models for stationary harmful processes is the which has been introduced by S. Dobrev, P. Flocchini, G. Prencipe and N. Santoro in 2001 ([25]). A black hole is a harmful node in the network that destroys any mobile agent visiting that node without leaving any trace. The objective of the Black Hole Search· problem is to identify the black hole without destroying too many agents and the main effort is to discover the minimal hypotheses under which it can be solved. Another effort has to do with producing fastest black hole search schemes. The problem has been initially investigated in asynchronous networks and introduced later in synchronous networks. In synchronous networks the most studied issue was that of achieving time optimal black hole search schemes. Recently it has been investigated in synchronous networks under very weak models (e.g., using agents with only constant memory) in which it is unsolvable in asynchronous networks. In this survey we discuss the computational issues and present algorithmic techniques for this problem. Since searching for a black hole in a network is closely related to exploration, rendezvous and leader election problems, the techniques presented here have a much wider range in distributed computing.