The impact of dynamic events on the number of errors in networks

In order to achieve routing in a graph, nodes need to store routing information. In the case of shortest path routing, for a given destination, every node has to store an advice that is an outgoing link toward a neighbor. If this neighbor does not belong to a shortest path then the advice is considered as an error and the node giving this advice will be qualified a liar. This article focuses on the impact of graph dynamics on the advice set for a given destination. More precisely we show that, for a weighted graph G of diameter D with n nodes and m   edges, the expected number of errors after MM edge deletions is bounded by O(n⋅M⋅D/m)O(n⋅M⋅D/m). We also show that this bound is tight when M=O(n)M=O(n). Moreover, for M′M′ node deletions, the expected number of errors is O(M′⋅D)O(M′⋅D). Finally we show that after a single edge addition the expected number of liars can be Θ(n)Θ(n) for some families of graphs.