Afficher la notice abrégée

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.identifierAlgorithms, simulation, combinatorics and optimization for telecommunications [MASCOTTE]
dc.contributor.authorNISSE, Nicolas
hal.structure.identifierLaboratoire de Recherche en Informatique [LRI]
dc.contributor.authorSOGUET, David
dc.date.accessioned2024-04-15T09:50:26Z
dc.date.available2024-04-15T09:50:26Z
dc.date.issued2009
dc.identifier.issn0178-2770
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198341
dc.description.abstractEnBlin et al. (TCS 2008) proposed a distributed protocol enabling the smallest possible number of searchers to clear any unknown graph in a decentralized manner. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. This paper deals with the smallest number of searchers that are necessary and sufficient to monotonously clear any unknown graph in a decentralized manner. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. We prove that a distributed protocol clearing any unknown $n$-node graph in a monotone connected way, in a decentralized setting, can achieve but cannot beat competitive ratio of $\Theta(\frac{n}{\log n})$, compared with the centralized minimum number of searchers. Moreover, our lower bound holds even in a synchronous setting, while our constructive upper bound holds even in an asynchronous setting.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Verlag
dc.subject.enGraph searching
dc.subject.enMobile agent
dc.subject.enMonotonicity
dc.subject.enCompetitive ratio
dc.title.enThe Cost of Monotonicity in Distributed Graph Searching
dc.typeArticle de revue
dc.identifier.doi10.1007/s00446-009-0089-1
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalDistributed Computing
bordeaux.page117-127
bordeaux.volume22
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00412063
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00412063v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Distributed%20Computing&rft.date=2009&rft.volume=22&rft.issue=2&rft.spage=117-127&rft.epage=117-127&rft.eissn=0178-2770&rft.issn=0178-2770&rft.au=ILCINKAS,%20David&NISSE,%20Nicolas&SOGUET,%20David&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée