Afficher la notice abrégée

The Impact of Edge Deletions on the Number of Errors in Networks

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorGLACET, Christian
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorILCINKAS, David
dc.date.accessioned2024-04-15T09:46:11Z
dc.date.available2024-04-15T09:46:11Z
dc.date.issued2011
dc.date.conference2011-12-13
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197987
dc.description.abstractEnIn this paper, we deal with an error model in distributed networks. For a target t, every node is assumed to give an advice, ie to point to a neighbour that takes closer to the destination. Any node giving a bad advice is called a liar. Starting from a situation without any liar, we study the impact of topology changes on the number of liars. More precisely, we establish a relationship between the number of liars and the number of distance changes after one edge deletion. Whenever l deleted edges are chosen uniformly at random, for any graph with n nodes, m edges and diameter D, we prove that the expected number of liars and distance changes is O(l^2Dn/m) in the resulting graph. The result is tight for l=1. For some specific topologies, we give more precise bounds.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 15th International Conference On Principles Of Distributed Systems
dc.subject.endynamic graph
dc.subject.enerrors and faults
dc.subject.enshortest path and routing
dc.title.enThe Impact of Edge Deletions on the Number of Errors in Networks
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-25873-2_26
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page378-391
bordeaux.volume7109
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleOPODIS 2011
bordeaux.countryFR
bordeaux.title.proceedingProceedings of the 15th International Conference On Principles Of Distributed Systems
bordeaux.conference.cityToulouse
bordeaux.peerReviewedoui
hal.identifierhal-00652051
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2011-12-16
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00652051v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2015th%20International%20Conference%20On%20Principles%20Of%20Distributed%20Systems&rft.date=2011&rft.volume=7109&rft.spage=378-391&rft.epage=378-391&rft.au=GLACET,%20Christian&HANUSSE,%20Nicolas&ILCINKAS,%20David&rft.genre=unknown


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