# GIH11

### Summary

**Christian Glacet, David Ilcinkas and Nicolas Hanusse** (2011) *The impact of edge deletions on the number of errors in networks.* In 15th International Conference on Principles of Distributed Systems (OPODIS). dec. Springer, pages 378-391. ((URL)) (PDF)

### 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, i.e. to point to a neighbor that take closer to the destination. Any node giving a bad advice is called \emph{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 {$\ell$} 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(\frac{\ell^2Dn}{m})$} in the resulting graph. The result is tight for {$\ell=1$}. For some specific topologies, we give more precise bounds.

### Bibtex entry

`@INPROCEEDINGS { GIH11,`

AUTHOR = { Christian Glacet and David Ilcinkas and Nicolas Hanusse },

TITLE = { The impact of edge deletions on the number of errors in networks },

BOOKTITLE = { 15th International Conference on Principles of Distributed Systems (OPODIS) },

PUBLISHER = { Springer },

LOCATION = { Toulouse, France },

VOLUME = { 7109 },

SERIES = { Lecture Notes in Computer Science },

PAGES = { 378-391 },

MONTH = { dec },

YEAR = { 2011 },

URL = { http://dx.doi.org/10.1007/978-3-642-25873-2_26 },

PDF = { http://www.labri.fr/perso/ilcinkas/publications/OPODIS2011Chr.pdf },

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, i.e. to point to a neighbor that take closer to the destination. Any node giving a bad advice is called \emph{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 {$\ell$} 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(\frac{\ell^2Dn}{m})$} in the resulting graph. The result is tight for {$\ell=1$}. For some specific topologies, we give more precise bounds. },

}