Memoryless search algorithms in a network with faulty advice

In this paper, we present a randomized algorithm for a mobile agent to search for an item stored at a node t 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 find 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 traversed by the agent before finding t is bounded from above by O(d+rk), where d is the distance between the initial and target nodes and r=q1−q. We also show that this expected number of steps can be significantly improved for particular topologies such as the complete graph and the torus.