Searching with mobile agents in networks with liars
In this paper, we present algorithms to search for an item s contained in a node of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I get to s?” by responding with the first edge on a shortest path to s. It may happen that some nodes, called liars, give bad advice. If the number of liars k is bounded, we show different strategies to find the item depending on the topology of the network. In particular we consider the complete graph, ring, torus, hypercube and bounded degree trees.
Hanusse, N. (Nicolas), Kranakis, E, & Krizanc, D. (Danny). (2000). Searching with mobile agents in networks with liars.