Nicolas Nisse

how to beat the random walk when you have a clock?

Abstract:

We study the problem of finding a destination node t by a mobile agent in an unreliable network. Each node is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. We focus on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. The performance of such strategies is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random regular graphs.

This is a joint work with N. Hanusse, D. Ilcinkas and A. Kosowski.