Sémidoc 25 novembre 2010

Thomas Morsellino (LaBRI)

 

25 novembre 2010
Puissance des réseaux radio anonymes : caractérisations.

 

 

Nous 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 ²) messages de taille O(∆ log n) bits.