Titre : Modélisation et étude de la puissance des systèmes distribués avec communication par liaison radio Equipe du LaBRI : Combinatoire et algorithmique Thème de recherche : Algorithmique distribuée Directeur de thèse : Yves Métivier Sujet. Ce travail s'inscrit dans le cadre général de l'algorithmique des systèmes distribués. Les algorithmes utilisés font l'objet de nombreuses descriptions dans des formalismes inspirés des langages classiques comme par exemple CSP. Ce cadre ne permet pas toujours de faire des preuves ``mathématiques'' des propriétés de ces algorithmes. On propose un formalisme original dans ce domaine : les réécritures de graphes et plus généralement les calculs locaux dans les graphes. De fait, il constitue un prolongement des travaux menés par P.Rosenstiehl et al. dans les années 70 et par D.Angluin dans les années 80 concernant les propriétés locales et les propriétés globales dans les réseaux et les graphes. On considère qu'un système distribué est codé par un graphe, et on associe à chaque sommet ou arête une étiquette (état). Une règle de calcul est définie par la donnée d'une boule de rayon 1 et de deux étiquetages de cette boule, donc elle est appliquée localement. Ainsi, un algorithme distribué est défini par la donnée d'un ensemble de telles règles. Le comportement du réseau est défini par un étiquetage initial et par une suite de pas de calcul. Dans ce cadre, des caractérisations ont été obtenues pour différents problèmes: - problème de l'élection qui consiste à particulariser exactement un sommet à partir d'un étiquetage initial, - problème de la détection de la terminaison, - problème de la reconnaissance, il s'agit alors de caractériser une famille de graphes par un étiquetage final à partir d'une configuration initiale uniforme. Cette étude a permis de montrer l'importance de deux algorithmes : celui de Mazurkiewicz et celui de Szymanski, Shy et Prewes. Deux outils sont déterminants : les revêtements et les quasi-revêtements. Le travail proposé dans le cadre de cette thèse consiste d'une part à étudier le problème du calcul de l'état global dans le modèle de Mazurkiewicz (et éventuellement dans la cadre d'une communication par échange de messages en mode asynchrone) et d'autre part à étudier certains problèmes énoncés ci-dessus dans un modèle de communication radio où en un pas de calcul un ensemble de sommets observent l'état d'un sommet et changent leurs propres états.