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 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/1-q. 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.
|Keywords||Data structure and algorithms, Distributed computing, Faulty networks, Graph, Random walks, Randomized algorithms|
Hanusse, N. (Nicolas), Kavvadias, D. (Dimitris), Kranakis, E, & Krizanc, D. (Danny). (2002). Memoryless search algorithms in a network with faulty advice.