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.
|Organisation||School of Computer Science|
Hanusse, N. (Nicolas), Kranakis, E, & Krizanc, D. (Danny). (2000). Searching with mobile agents in networks with liars.