Mostrar el registro sencillo del ítem

Locating a Target with an Agent Guided by Unreliable Local Advice

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierAlgorithms, simulation, combinatorics and optimization for telecommunications [MASCOTTE]
dc.contributor.authorNISSE, Nicolas
dc.date.accessioned2024-04-15T09:49:12Z
dc.date.available2024-04-15T09:49:12Z
dc.date.issued2010
dc.date.conference2010-07
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198238
dc.description.abstractEnWe 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 et al [20, 21]. 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 liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2^Ω(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 R/A, makes use of a timer (step counter) to alternate between phases of ignoring advice (R) and following advice (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 Δ-regular graphs (an important class of expanders). For the ring, R/A is shown to achieve an expected searching time of 2d+k^Θ(1) for a worst-case distribution of liars, which is polynomial in both d and k. For random Δ-regular graphs, the expected searching time of the 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 Ω(log n) steps holds for all d,k = Ω(log logn) in random Ω-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 R/A strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in d and k.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherACM New York, NY, USA
dc.source.titleProceedings of the 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
dc.subject.enDistributed Computing
dc.subject.enMobile Agent
dc.subject.enRandom Walks
dc.subject.enExpanders
dc.subject.enFaulty Networks
dc.title.enLocating a Target with an Agent Guided by Unreliable Local Advice
dc.typeCommunication dans un congrès
dc.identifier.doi10.1145/1835698.1835781
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page355-364
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titlePODC 2010
bordeaux.countryCH
bordeaux.title.proceedingProceedings of the 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
bordeaux.conference.cityZurich
bordeaux.peerReviewedoui
hal.identifierhal-00516695
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00516695v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2029th%20Annual%20ACM%20SIGACT-SIGOPS%20Symposium%20on%20Principles%20of%20Distributed%20Computing&rft.date=2010&rft.spage=355-364&rft.epage=355-364&rft.au=HANUSSE,%20Nicolas&ILCINKAS,%20David&KOSOWSKI,%20Adrian&NISSE,%20Nicolas&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem