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{sup}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.