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+r(k)), where d is the distance between the initial and target nodes and r = q/1-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. (C) 2008 Elsevier B.V. All rights reserved.
randomized algorithms distributed computing mobile agent computing graph searching random walks faulty networks