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

Titre:   
Problèmes de l'énumération et de l'élection dans les réseaux radio anonymes

Date 2010-11-25  14:00-15:00
NomProblèmes de l'énumération et de l'élection dans les réseaux radio anonymes 
DescriptionNous traitons des problèmes de l'énumération et de l'élection sur les réseaux radio multi-sauts. Nous considérons un modèle asynchrone de communication radio dans lequel chaque processus émet un message et tous ses voisins l'entendent après un temps fini, mais inconnu. Ce délai dépend du temps pris par les couches réseau inférieures pour assurer l'acheminement des messages. Dans cette présentation, nous caractérisons les graphes où nous pouvons résoudre ces problèmes et nous présentons un algorithme d'énumération et un autre d'élection. Pour ces deux problèmes, nous soulignons l'importance de la connaissance initiale. Pour le problème de l'énumération, chaque processus connait seulement la taille du graphe et, contrairement aux résultats connus jusqu'à présent, le nombre de ses voisins lui est inconnu. Tandis que pour le problème de l'élection, nous montrons que cette connaissance n'est pas suffisante ; notre algorithme suppose que chaque processus connait initialement une carte du réseau. Étant donné un graphe de degré maximum ∆ avec n noeuds et m arêtes, nos algorithmes émettent O(mn^2) messages de taille O(∆ log n) bits.  
LieuAmphi 
ContactThomas Morsellino 



Aucun document lié à cet événement.

Retour
Retour à l'index