Evènement pour le groupe GT Graphes et Applications


Date 2011-10-28  14:30-15:00
TitreÉnumération et élection dans les environnements de diffusion multisauts anonymes 
RésuméNous étudions les problèmes de l'énumération et de l'élection dans des environnements de diffusion multisauts. Nous considérons un modèle de communication asynchrone dans lequel chaque noeud du réseau diffuse un message et son voisinage le reçoit après un délai de temps arbitraire inconnu. Ce délai dépend du temps pris par les couches réseaux pour assurer l'acheminement du message. Dans ce travail, nous présentons les conditions nécessaires que doivent satisfaire les graphes pour résoudre ces problèmes puis nous montrons que ces conditions sont suffisantes en fournissant un algorithme pour l'énumération et un algorithme pour l'élection. Pour ces deux problèmes, nous mettons en avant l'importance de la connaissance initiale. Concernant le problème de l'énumération, chaque noeud connait le nombre de noeuds du graphe et, contrairement aux travaux existants, n'a pas connaissance de son voisinage. Pour le problème de l'élection, nous montrons que cette connaissance n'est pas suffisante. Nous proposons un algorithme dans lequel nous supposons que chaque noeud connait une carte du graphe (sans connaitre sa position dans ce graphe). Nos algorithmes offrent une meilleure complexité (mémoire et messages) en regard des travaux existants la réduisant ainsi d'exponentielle à polynomiale. 
LieuSalle 178 
OrateurThomas Morsellino 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index