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. },
}