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

Christian Glacet (1, 2) , Nicolas Hanusse (1, 2) , David Ilcinkas (1, 3)

1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique
3 Combinatoire et Algorithmique

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.

Mots clés: dynamic graph; errors and faults; shortest path and routing

Domaines: Algorithme et structure de données [cs.DS]

Christian Glacet, Nicolas Hanusse, David Ilcinkas. The Impact of Edge Deletions on the Number of Errors in Networks. OPODIS 2011, Dec 2011, Toulouse, France. pp.378-391, ⟨10.1007/978-3-642-25873-2_26⟩. ⟨hal-00652051⟩