The Impact of Edge Deletions on the Number of Errors in Networks
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...