Evènement pour le groupe Algorithmique Distribuée


Date 2016-03-07  14:00-15:00
TitreTime vs. Information Tradeoffs for Leader Election in Anonymous Trees 
RésuméDans cette présentation je donnerai des résultats concernant l'élection de leader dans des arbres anonymes. Dans le modèle utilisé, l'ensemble des nœuds doivent produire en sortie un chemin simple vers l'un d'entre eux, ce dernier sera alors qualifié de leader. Le cas particulier étudié est celui de l'élection lorsque le temps alloué est inférieur au diamètre de l'arbre considéré. Si aucune information supplémentaire n'est accessible, les nœuds ne pouvant pas avoir une vision complète du réseau, l'élection est impossible et ce quel que soit l'algorithme utilisé. L'étude proposée concerne donc le compromis entre la quantité d'information initialement requise par les nœuds et le temps leur étant alloué pour réaliser l'élection. Le modèle utilisé est celui des algorithmes avec conseil dans lequel un oracle ayant une connaissance complète du réseau, fournit un conseil unique sous forme d'une chaîne binaire, à l'ensemble des nœuds avant que ceux-ci n'initient leurs calculs. Pour la majorité des valeurs de temps nos bornes inférieures et supérieures sont proches à un facteur multiplicatif près, ou diffèrent seulement d'un facteur logarithmique. Je présenterai le détail des résultats ainsi que les outils utilisés pour l'établissement de deux bornes me paraissant représentatives de cette étude.  
Lieu178 
OrateurChristian Glacet 
UrlCNR - IEIIT, Torino, Italy 



Aucun document lié à cet événement.

Retour
Retour à l'index