GLACET, Christian; HANUSSE, Nicolas; ILCINKAS, David

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

Métadonnées

Licence d’utilisation du document

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

Langue

Communication dans un congrès

Ce document a été publié dans

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

Résumé en anglais

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.< Réduire

Mots clés en anglais

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

Project ANR

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

Origine

Importé de hal

Unités de recherche

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