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. |