Réécriture de graphes et algorithmique distribuée

Un système distribué peut être représenté par un graphe étiqueté : les sommets correspondent aux processeurs, les arêtes aux liens de communication et les étiquettes associées aux sommets codent les états des processeurs. Un algorithme distribué est alors décrit par un système de règles de transition locale où l'étiquette suivante d'un sommet est fonction de son étiquette actuelle et de celles de ses voisins (réétiquetage local). Les réétiquetages opérant sur des voisinages disjoints se déroulent en parallèle, de manière asynchrone. Dans ce cadre, on étudie la réalisabilité et non-réalisabilité des tâches distribuées. Nous illustrerons notre méthode en nous intéressant en particulier à certains problèmes spécifiques aux systèmes distribués (élection d'un noeud, reconnaissancede certaines propriétés topologiques du graphe sous-jacent au réseau, calcul de métriques du réseau comme par exemple la taille ou le diamètre). Dans tous ces cas, on présente une caractérisation complète de ce qui est réalisable par calcul distribué en fonction de la topologie du graphe sous-jacent mais également du degré de connaissance qu'a le réseau sur lui-même ("connaissance structurelle"). Ces conditions nécessaires et suffisantes sont principalement exprimées en termes de fermetures par "similarités" des familles de réseaux considérées. Ces "similarités" sont décrites de manière combinatoire à l'aide de morphismes de graphes particuliers : les revêtements et les quasi-revêtements. Les preuves des conditions nécessaires emploient des techniques de simulation à base de revêtements et quasi-revêtements. Les algorithmes distribués présentés pour les preuves des conditions suffisantes se fondent essentiellement sur un algorithme de cartographie du réseau sous-jacent. Celui-ci est construit à partir des extensions d'un algorithme d'énumération de A. Mazurkiewicz et d'un algorithme de détection des propriétés stables de Shy, Szymanski et Prywes.A distributed system can be modelized by a labelled graph : processes as vertices, communication links as edges and labels as processes' states. A distributed algorithm is then described as a local transition system where rules define the label of a vertex according to its current label and to its neighbours' labels (local relabelling). Relabellings operating on disjoint neighbourhood are executed in parallel, asynchronously. In this framework, we study the feasibility and non-feasibility of distributed tasks. Our method is illustrated by investigating in particular some problems that are specific todistributed systems (election of a node, recognition of some topological properties of the underlying graph, computations of mettrics of the network such as the size or the diameter). In all above cases, we give a full characterization of what is feasible with distributed computations according to the topology of the underlying graph but also according to the amount of knowledge that the network has about its own topology ("structural knowledge"). These characterizations are mainly expressed in terms of "similarities" of the networks families that we consider. These "similarities" are combinatorially described with the help of special kind of graphs morphisms : coverings and quasicoverings. The proof of necessary conditions are done by quasi-covering and coveringbasedsimulation techniques. The distributed algorithms we describe for proving sufficient conditions are essentially based upon a cartography algorithm. This algorithm is constructed from the extensions of an enumeration algorithm by A. Mazurkiewicz and an algorithm for detecting stable properties by Shy, Szymanski et Prywes