Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
The Impact of Edge Deletions on the Number of Errors in Networks.
du groupe Algorithmique Distribuée

Date 2012-01-16  14:00-15:00
TitreThe Impact of Edge Deletions on the Number of Errors in Networks.  
RésuméIn this talk 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 take 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^2 D n / m) in the resulting graph. The result is tight for l = 1. For some specific topologies, we give more precise bounds. This is joint work with Nicolas Hanusse and David Ilcinkas. Orateur: Christian Glacet 
Lieus. 076 
OrateurChristian Glacet 



Aucun document lié à cet événement.

Retour
Retour à l'index