The Impact of Edge Deletions on the Number of Errors in Networks
GLACET, Christian
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
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]
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
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
GLACET, Christian
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
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]
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
< Reduce
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
Language
en
Communication dans un congrès
This item was published in
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
English Abstract
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 ...Read more >
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.Read less <
English Keywords
dynamic graph
errors and faults
shortest path and routing
ANR Project
Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
Origin
Hal imported