Nous présentons dans ce mémoire de thèse d'habilitation une étude sur des algorithmes distribués asynchrones de contrôle et d'ordonnancement. Un algorithme de contrôle établit une structure virtuelle sur un réseau de sites communicants. Nous faisons le choix %délibéré de faire un minimum d'hypothèses sur les connaissances de chaque site. De même, nous évitons autant que possible d'utiliser des mécanismes conduisant à des attentes qui peuvent être pénalisantes comme, par exemple, l'utilisation de synchroniseurs. Ces choix conduisent à privilégier les modes de fonctionnement essentiellement locaux. %dépendant le moins possible de l'état du reste du réseau. Nous introduisons toutefois une limite à cette démarche, dans ce travail, nous ne considérons que des algorithmes déterministes. Dans ces circonstances, un problème essentiel de l'algorithmique distribuée est l'établissement d'une structure de contrôle couvrant la totalité du réseau, dans laquelle chaque site distingue certains de ses voisins de façon spécifique. Après avoir rappelé des notions fondamentales en partie I, nous présentons dans la première partie, trois de nos algorithmes de construction d'arbre couvrant avec contraintes, ces dernières apportant une plus grande efficacité à la structure de contrôle établie. En particulier, nous considérons la contrainte de poids total minimum qui caractérise plutôt une recherche économique, celle de diamètre minimum qui concerne l'efficacité à la fois en temps mais aussi évidemment en messages et la contrainte de degré minimal qui permet par exemple d'utiliser des équipements d'interconnection moins coûteux. Dans la troisième partie nous présentons deux de nos heuristiques pour la résolution du problème de l'ordonnancement distribué en ligne, avec arrivées sporadiques, d'abord de tâches indépendantes puis de tâches avec dépendances non cycliques. Nous montrons que là encore, la structure d'arbre peut être utilisée de façon bénéfique. En particulier, dans des réseaux de taille arbitrairement grande, des arbres de plus courts chemins limités aux voisins relativement proches peuvent être utilisés pour définir un concept nouveau et prometteur ,: la Sphère de Calcul. Cette Sphère de Calcul limite le nombre de messages échangés et le temps de calcul. Tout au long de ce mémoire nous présentons des algorithmes nouveaux, voire pionniers dans leurs domaine. De nombreux développements sont possibles, certains déjà réalisés par nous-même ou par d'autres auteurs, d'autres sont des problèmes ouverts (recherche d'algorithmes optimaux par exemple).

Les réseaux spatiaux sont des réseaux dans lesquels les sommets occupent une position dans l'espace Euclidien. Les interactions dans ces réseaux sont déterminées par cette géometrie sous-jacente des sommets. Les réseaux de communications offrent un vaste champ d'application et une source de nouveaux modèles autour de ce thème. La thèse aborde trois sujets dans des domaines differents. Le premier concerne l'étude de certains arbres couvrant géométriques de processus ponctuels de Poisson. Ces travaux portent notamment sur le phenomene "petit monde", les arbres couvrants radiaux et l'arbre couvrant minimal. Un autre sujet de recherche porte sur la stabilité stochastique de réseaux de files d'attente pour lesquelles les files ont des interactions spatiales. La dernière partie de la thèse aborde des thèmes reliés à la géometrie stochastique: une étude du modèle de feuilles mortes et un travail sur la sensibilité de fonctionnelles de processus ponctuels de Poisson.

Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce document s'intéresse à l'approche auto-stabilisante qui vise à concevoir des algorithmes se ''réparant d'eux-même ' en cas de fautes transitoires, c'est-à-dire de pannes impliquant la modification arbitraire de l'état des processus. Il se focalise sur deux contextes différents, couvrant la majeure partie de mes travaux de recherche ces dernières années. La première partie du document est consacrée à l'algorithmique auto-stabilisante pour les réseaux de processus. La seconde partie du document est consacrée quant à elle à l'algorithmique auto-stabilisante pour des entités autonomes (agents logiciels, robots, etc.) se déplaçant dans un réseau.

Les réseaux de capteurs sont des réseaux particuliers composés d'objets contraints en ressources. Ils possèdent une faible puissance de calcul, une faible puissance de transmission, une faible bande passante, une mémoire de stockage limitée ainsi qu'une batterie à durée de vie limitée. Afin d'intégrer de tels réseaux dans l'internet des objects, de nouveaux protocoles ont été standardisés. Parmi ces protocoles, le protocole RPL (pour Routing Protocol for Low Power and Lossy Networks). Ce protocole est destiné a construire une topologie logique de routage appelée DODAG. Dans cette thèse, nous abordons l'aspect acheminement de données qui considère une topologie de routage arborescente. L'acheminement des données se fait donc de saut en saut d'un enfant à son parent (ou d'un parent à son enfant). Optimiser la construction du DODAG revient donc à construire un arbre couvrant selon une contrainte donnée. Un arbre couvrant est une structure communicante qui permet de maintenir un unique chemin entre toutes paires de noeuds tout en minimisant le nombre de liens de communication utilisés. De plus, nous considérons les contraintes des réseaux de capteurs telles qu'une batterie déchargée et la variabilité du lien radio comme des fautes transitoires. Ceci nous conduit par conséquent à construire une structure couvrante tolérante aux fautes transitoires. L'auto-stabilisation est une branche de l'algorithmique distribuée qui assure qu'à la suite d'une ou de plusieurs fautes transitoires, le système va retrouver de lui-même un comportement correcte au bout d'un temps fini. L'objectif de cette thèse est de proposer des algorithmes auto-stabilisants dédiés aux réseaux de capteurs. / Spanning Trees from theory to practiceSelf-Stabilizing algorithms and sensor networksAbstract : Sensor networks are composed of ressources constrained equipments. They have low computing power, low transmission power, low bandwidth, limited storage memory and limited battery life.In order to integrate such networks in the Internet of things, new protocols were standardized such as RPL protocol (for Routing Protocol for Low Power and Lossy Networks). This protocol is intended to build a logical routing topology called DODAG (for Destination Oriented Directed Acyclic Graph). In this thesis, we discuss the data routing aspect by considering a tree routing topology. Thus, the routing of data is hop by hop from a child to its parent (or from a parent to its child). Optimize the construction of the DODAG is therefore to build a spanning tree in a given constraint. A spanning tree is a connecting structure that maintains a unique path between all pairs of nodes while minimizing the number of used communication links. Furthermore, we consider the constraints of sensor networks, such as a dead battery and the variability of the radio link as transient faults. This leads us to build a covering structure tolerant to transient faults. The self-stabilization is a branch of distributed algorithms that ensures that following one or more transient faults, the system will find itself a correct behavior after a finite time.The objective of this thesis is to propose self-stabilizing algorithms dedicated to sensor networks. The contributions of this thesis are:In the first part of the thesis, we proposed a self-stabilizing algorithm for the construction of a minimum diameter spanning tree.This construction is natural when we want to minimize the communication delay between a root and all other network nodes. Our algorithm has several advantages. First, our algorithm is limited to memory occupation of O(log n) bits per node, reducing the previous result of an n factor while maintaining a polynomial convergence time. Then, our algorithm is the first algorithm for minimum diameter spanning tree that works as an unfair distribution demon. In other words, we make no restriction on the asynchronous network behavior. In the second part of the thesis, we are interested in the unstable topology built by RPL protocol (DODAG). Our solution is to place an additional constraint on the number of children a node can accept during the construction of the DODAG. This constraint has the effect of reducing the rate of parent change and consequently to improve the protocol performance in terms of packet delivery rate, delay of communication and power consumption. In addition, we implemented a mechanism to update the information of the downward routes in RPL. Furthermore, our solution has the advantage of not generating overhead because we use existing control messages provided by RPL to implement it. Finally, this contribution is twofold since we validated our solution both by simulations and experiments.

Nous étudions le déterminant du laplacien sur les fibrés vectoriels sur les graphes et l'utilisons, en lien avec des techniques d'analyse complexe discrète, pour comprendre des modèles de physique statistique. Nous calculons certaines constantes de réseaux, construisons des limites d'échelles d'excursions de la marche aléatoire à boucles effacées sur les surfaces, et étudions certains champs gaussiens et processus déterminantaux. / We study the determinant of the Laplacian on vector bundles on graphs and use it, combined with discrete complex analysis, to study models of statistical physics. We compute exact lattice constants, construct scaling limits for excursions of the loop-erased random walk on surfaces, and study some Gaussian fields and determinantal processes.

Ce mémoire donne un aperçu de mes travaux de recherche depuis la thèse. La thématique générale est la mécanique statistique, qui a pour but de comprendre le comportement macroscopique d'un système physique dont les interactions sont décrites au niveau microscopique. De nombreux modèles appartiennent à la mécanique statistique; nos résultats se concentrent sur le modèle d'Ising, le modèle de dimères et les arbres couvrants en dimension deux. Ces trois modèles ont la particularité d'être exactement solubles, c'est-à-dire qu'il existe une expression exacte et explicite pour la fonction de partition. Ce mémoire décrit et met en perspective les résultats de mes publications, et donne les étapes principales des démonstrations.