GLACET, Christian; HANUSSE, Nicolas; ILCINKAS, David

doi:10.1007/978-3-642-25873-2_26

Metadatos

Licencia de uso del documento

GLACET, Christian
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

HANUSSE, Nicolas
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

ILCINKAS, David
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique

Idioma

Communication dans un congrès

Este ítem está publicado en

Proceedings of the 15th International Conference On Principles Of Distributed Systems, Proceedings of the 15th International Conference On Principles Of Distributed Systems, OPODIS 2011, 2011-12-13, Toulouse. 2011, vol. 7109, p. 378-391

Springer Berlin / Heidelberg

Resumen en inglés

In 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.< Leer menos

Palabras clave en inglés

dynamic graph

errors and faults

shortest path and routing

URI

https://oskar-bordeaux.fr/handle/20.500.12278/197987

DOI

http://dx.doi.org/10.1007/978-3-642-25873-2_26

Proyecto ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800