20021201
Memoryless search algorithms in a network with faulty advice
Publication
Publication
In this paper, we present a randomized algorithm for a mobile agent to search for an item t stored at 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 t?" by responding with the first edge on a shortest path to t. It may happen that some nodes, called liars, give bad advice. We investigate a simple memoryless algorithm which follows the advice with some fixed probability q > 1/2 and otherwise chooses a random edge. If the degree of each node and number of liars k are bounded, we show that the expected number of edges to follow in order to reach t is bounded from above by O(d + rk), where d is the distance between the initial and target node and r = q/1q. We also show that this expected number of steps can be significantly improved for particular topologies such as the complete graph, the torus, and the spider graph.
Additional Metadata  

Data structure and algorithms, Distributed computing, Faulty networks, Graph, Random walks, Randomized algorithms  
Organisation  School of Computer Science 
Hanusse, N. (Nicolas), Kavvadias, D. (Dimitris), Kranakis, E, & Krizanc, D. (Danny). (2002). Memoryless search algorithms in a network with faulty advice.
