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

Nicolas Hanusse 1, 2 David Ilcinkas 1, 2 Adrian Kosowski 1, 2, 3 Nicolas Nisse 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse {\it et al.}~\cite{HKK00,HKKK08}. Each node of the network 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 \emph{liars}, give advice which is incorrect. It is known that for an $n$-node graph $G$ of maximum degree $\Delta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\Omega(\min\{d,k\})}$, for any $d,k=O(\log n)$, even when $G$ is a tree. This paper focuses 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 strategy which we put forward, called \algo{R/A}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{R}) and following advice (\algo{A}) for a certain number of steps. No knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. The performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). For the ring, \algo{R/A} is shown to achieve an expected searching time of $2d+k^{\Theta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. For random $\maxdeg$-regular graphs, the expected searching time of the \algo{R/A} strategy is $O(k^3 \log^3 n)$ a.a.s. The polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\Omega (\log n)$ steps holds for all $d,k=\Omega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. Finally, we study oblivious strategies which do not use any memory (in particular, with no timer). Such strategies are essentially a form of a random walk, possibly biased by local advice. We show that such biased random walks sometimes achieve drastically worse performance than the \algo{R/A} strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$
Document type :
Reports
[Research Report] RR-7210, INRIA. 2010, pp.19
Liste complète des métadonnées

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/inria-00458808
Contributor : Nicolas Nisse <>
Submitted on : Monday, February 22, 2010 - 1:20:02 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Thursday, October 18, 2012 - 3:36:14 PM

File

RR-7210.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00458808, version 1

Citation

Nicolas Hanusse, David Ilcinkas, Adrian Kosowski, Nicolas Nisse. How to beat the random walk when you have a clock?. [Research Report] RR-7210, INRIA. 2010, pp.19. 〈inria-00458808〉

Share

Metrics

Record views

584

Files downloads

210