Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance \Delta+1 agents are needed and suffice, and the cost is \Theta(n^2), where \Delta is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is \Theta(n^2); and with complete topological knowledge only two agents suffice and the cost is Theta(nlogn). All the upper-bound proofs are constructive.

Searching for a black hole in arbitrary networks: optimal mobile agents protocols

PRENCIPE, GIUSEPPE;
2006-01-01

Abstract

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance \Delta+1 agents are needed and suffice, and the cost is \Theta(n^2), where \Delta is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is \Theta(n^2); and with complete topological knowledge only two agents suffice and the cost is Theta(nlogn). All the upper-bound proofs are constructive.
2006
Dobrev, Stefan; Flocchini, Paola; Prencipe, Giuseppe; Santoro, Nicola
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/103458
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 57
  • ???jsp.display-item.citation.isi??? 39
social impact