Дисертації з теми "Consensus distribué"

Les architectures régulières intégrant plusieurs cœurs de traitement sont davantage utilisées dans les systèmes embarqués. Dans cette thèse, on s'intéresse aux mécanismes d'optimisation d'énergie dans des architectures avec une dimension étendue; pour faire face aux problèmes de variabilité technologique et aux changements du contexte applicatif, le processus d'optimisation se déroule en temps réel. Des capteurs in-situ détectent le degré de dégradation du circuit. Quant a la variabilité applicative, des moniteurs d'activité sont insérés sur un niveau architectural pour estimer la charge de travail engendrée par l'application en cours et la consommation qui en découle. Nous avons développé une méthode systématique pour l'intégration de ces capteurs avec un moindre coût en surface. Leurs sorties alimentent un processus d'optimisation basé sur la théorie de consensus et dupliqué dans chaque cœur. Ce contrôle vise à fixer la meilleure configuration locale à chaque cœur permettant d'optimiser la consommation globale du système tout en respectant les contraintes temps réel de l'application en cours. Ce schéma opère d'une manière complètement distribuée afin de garantir la scalabilité de notre solution, et donc sa faisabilité, compte tenu de la complexité des circuits actuels et futurs
Regular architectures embedding several processing elements are increasingly used in embedded systems. They require careful design to avoid high power consumption and to improve their flexibility. This thesis work deals with optimization mechanisms of large scale architectures; to meet variability issues, optimization is processed at run-time. The target design implements in-situ features to collect physical information about its yield and to monitor application workload and generated consumption. As for workload monitoring, we use activity counters connected at architecture level to a set of critical signals. We developed an automated method to optimally place these features with a minimal area overhead. The collected information are used further jointly with a power model to estimate the dissipated power and then driven appropriate optimization process. Optimal frequency for each core is set by means of a distributed controller based on consensus theory. The resulting settings aim to reduce the whole system power while fulfilling application constraints. The scheme needs to be fully distributed to garantee the control scalability, and so feasibility, as the number of cores scales

So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, n processes use l different identifiers, where 1 l n. We call this model homonymous model. To determine the power of homonymous model as well as the importance of identifiers in distributed computing, this thesis studies the consensus problem, one of the most famous distributed computing problem. We give necessary and sufficient conditions on the number of identifiers for solving consensus in a distributed system with t faulty processes in the synchronous case. We show that in crash, send omission and general omission failures model, the uniform consensus is solvable even if processes are anonymous. Thus, identifiers are not useful in that case. However identifiers become important in Byzantine failures model: 3t + 1 identifiers is necessary and sufficient for Byzantine agreement. Surprisingly the number of identifiers must be greater than n+3t 2 in presence of three facets of uncertainty: partial synchrony, Byzantine failures and homonyms. This demonstrates two differences from the classical model (which has l = n): there are situations where relaxing synchrony to partial synchrony renders agreement impossible, and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement.

L'informatique moderne est distribuée. La distribution du calcul résulte parfois d'un besoin applicatif lorsque l'objectif est de connecter des ordinateurs distants. Parfois, elle naît du besoin de tolérer des défaillances. En effet, pour éviter qu'une application ne soit à la merci de la défaillance d'une machine, le calcul est dupliqué sur plusieurs machines. Au coeur de tout calcul réparti repose une forme de coordination. Le fait même que des ordinateurs aient une tâche commune implique un besoin de se concerter avant d'accomplir certaines tâches. Nous étudions les problèmes de coordination dans le modèle asynchrone, sans hypothèses sur des bornes de vitesse d'exécution des processeurs ou de transmission des messages. Les processus peuvent défaillir à n'importe quel moment. Le degré de coordination qui peut être atteint en fonction du degré d'incertitude du système est la question principale de cette thèse. Trois formes de coordination sont considérées : l'accord ensembliste, le renommage et le consensus simultané. Dans un premier temps, nous proposons différentes réductions algorithmiques entre ces problèmes, afin de prouver dans quelles conditions une solution à l'un de ces problèmes permet d'obtenir une solution à un autre problème. Nous étudions ensuite des hypothèses nécessaires et suffisantes sur la détection de défaillances permettant de résoudre les problèmes d'accord. Le formalisme utilisé ici est celui des détecteurs de défaillances. Enfin, nous proposons un autre point de vue sur les détecteur de défaillances. Nous caractérisons la puissance de calcul amenée par ces détecteurs par une restriction des exécutions du modèle itéré de Gafni.

Cette thèse traite de l'identification des paramètres du point de vue de l'optimisation et du contrôle de suivi distribué des systèmes multi-agents d'ordre fractionnaire (FOMASs) en tenant compte des retards, des perturbations externes, de la non-linéarité inhérente, des incertitudes des paramètres et de l'hétérogénéité dans le cadre d'une topologie de communication fixe non dirigée / dirigée. Plusieurs contrôleurs efficaces sont conçus pour réaliser avec succès le contrôle de suivi distribué des FOMASs dans différentes conditions. Plusieurs types d'algorithmes d'optimisation de l'intelligence artificielle et leurs versions modifiées sont appliquées pour identifier les paramètres inconnus des FOMASs avec une grande précision, une convergence rapide et une grande robustesse. Il est à noter que cette thèse fournit un lien prometteur entre la technique d'intelligence artificielle et le contrôle distribué
This thesis deals with the parameter identification from the viewpoint of optimization and distributed tracking control of fractional-order multi-agent systems (FOMASs) considering time delays, external disturbances, inherent nonlinearity, parameters uncertainties, and heterogeneity under fixed undirected/directed communication topology. Several efficient controllers are designed to achieve the distributed tracking control of FOMASs successfully under different conditions. Several kinds of artificial intelligence optimization algorithms andtheir modified versions are applied to identify the unknown parameters of the FOMASs with high accuracy, fast convergence and strong robustness. It should be noted that this thesis provides a promising link between the artificial intelligence technique and distributed control

De nos jours, le travail collaboratif a pris une place très importante dans plusieurs domaines, et notamment dans le domaine du télédiagnostic médical. Et la cohérence des données partagées est un enjeu primordial dans ce type d'application. De plus, pour garantir la cohérence des données, l'utilisation d'un algorithme de consensus est un élément indispensable dans les plateformes collaboratives. Nous présentons ici un nouvel algorithme de consensus, nommé FLC, permettant de garantir la cohérence des données partagées dans les systèmes distribués collaboratifs complètement asynchrones. Notre algorithme est tolérant aux pannes et a pour objectif d'améliorer la performance de consensus et notamment lorsque les processus participants tombent en panne. Ce nouvel algorithme utilise l'oracle leader Omega pour contourner le résultat d'impossibilité du théorème FLP. L'algorithme est décentralisé et adopte le modèle de pannes crash-stop. L'algorithme FLC s'appuie sur deux idées principales. La première propose de réaliser, au début de chaque cycle d'exécution, une phase simple d'élection de processus leader garantissant l'existence d'un seul leader par cycle. La deuxième bénéficie de la stabilité du système et plus particulièrement du fait que le processus leader ne tombe pas en panne d'un consensus à l'autre. Les performances de notre algorithme ont été analysées et comparées à celles des algorithmes les plus connus dans le domaine. Les résultats obtenus par simulation en utilisant la plateforme Neko ont montré que notre algorithme donne les meilleures performances lorsque le réseau utilisé est un réseau multicast et qu'aucun processus ne tombent en panne ainsi que pour les situations dans lesquelles l'algorithme de consensus subit une ou plusieurs pannes de processus coordinateurs/leaders
Nowadays, collaborative work took a very important place in many fields and particularly in the medicaltelediagnosis field. The consistency of shared data is a key issue in this type of applications. Moreover, itis essential to use a consensus algorithm to ensure data consistency in collaborative platforms. We presenthere our new consensus algorithm FLC that helps to ensure data consistency in asynchronous collaborativedistributed systems. Our algorithm is fault tolerant and aims to improve the performance of consensus ingeneral and particularly in the case of process crashes. The new algorithm uses the leader oracle tocircumvent the impossibility result of the FLP theorem. It is decentralized and considers the crash-stop failuremodel. The FLC algorithm is based on two main ideas. The first is to perform, at the beginning of eachround, a simple election phase guaranteeing the existence of only one leader per round. The second is totake advantage of system stability and more particularly of the fact that the leader does not crash betweentwo consecutive consensus runs. The performance of our algorithm was analyzed and compared to the mostknown algorithms in the domain. The results obtained by simulation, using the Neko platform, demonstratedthat our algorithm gave the best performance when using a multicast network in the best case scenario and insituations where the algorithm undergoes one or more crashes of coordinators/leaders processes

Cette thèse présente une contribution sur les problèmes de contrôle de réseaux d'irrigations en tenant compte des contraintes de communication grâce à une approche multicouches d’intelligence distribuée. Les analyses détaillées de chaque couche avec les résultats analytiques et les simulations seront décrites dans les différents chapitres. Ils mettent l'accent sur l'intérêt de l'approche multicouches, plus précisément sur son efficacité et sa fiabilité pour la supervision, l'optimisation multi-objectifs et le contrôle coopératif distribué sur des systèmes complexes de transport d'eau.La première couche analysé est le réseau hydraulique composé de canaux d’écoulements à surface libre, de sous-réseaux maillés de tuyaux sous pression et des structures hydrauliques (pompes vannes, ..). En intégrant les équations de Saint-Venant pour décrire l’écoulement physique des fluides en surface libre et la méthode Lattice Boltzmann pour la simulation du fluide, nous obtenons un modèle non linéaire discret pour les canaux à surface libre. Les structures hydrauliques sont généralement traitées comme des limites internes des biefs (tronçons) et modélisées par des relations entre les variables de flux et de pression.Permettant l'échange d'informations entre les éléments du système de contrôle, le réseau de communication sera considéré comme la deuxième couche. La résolution des problèmes d’hétérogénéités des systèmes et des communications (par exemple les retards de diffusion dans le réseau, la perte de paquets, la consommation d'énergie) sera étudié en introduisant une architecture de réseau hybride avec un routage dynamique basé sur les exigences de Qualité de Service (QoS) des applications de contrôle. Pour le routage dynamique dans le réseau, une composition pondérée de certaines métriques standards est proposée afin que le protocole de routage utilisant cette métrique composite converge sans boucle avec une « route » optimum. Grâce à différents scénarios de simulation, plusieurs critères de performance du réseau ont été évalués. La comparaison des résultats de simulation permet de valider l'intérêt de cette approche de composition pour le routage dynamique.Une troisième couche propose un système de contrôle réactif optimal développé pour la régulation du réseau d'irrigation dans un modèle étendue à grande échelle : Distributed Cooperative Model Predictive Control (DCMPC). Cette partie aborde la mise en œuvre de différentes stratégies de contrôle (centralisées, décentralisées et distribuées) et intègre la communication coopérative entre les contrôleurs MPC locaux afin d’améliorer les performances global es du système. La gestion de la divergence dans l'échange d'informations entre les contrôleurs est considérée comme un problème de consensus et résolue en utilisant un protocole de consensus asynchrone. Cette approche du contrôle distribué basée sur le paradigme des systèmes multi-agents, fournit une solution garantissant que tous les contrôleurs aient une vue cohérente de certaines valeurs des données nécessaires pour le calcul de décision. Un cas d’application sur un canal d'irrigation est étudié dans les simulations. La comparaison des résultats de simulations valide les avantages de l'approche du contrôle distribué coopératif par rapport aux autres stratégies de contrôle
This thesis presents control problems of irrigation network with communication constraints and a multi-layer approach to solve these problems in a distributed manner. Detailed discussions of each layer with analytical and simulation results are described throughout several chapters. They emphasize the potential interest of the multi-layer approach, more precisely its efficiency and reliability for supervision, multi-objective optimization and distributed cooperative control of complex water transport systems. Conventionally, the first layer to be considered is the hydraulic network composed of free-surface channels, hydraulic structures and mesh subnetwork of pressurized pipes. By coupling the Saint-Venant equations for describing the physics of free-surface fluid and the Lattice Boltzmann method for the fluid simulation, a discrete-time nonlinear model is obtained for channel reaches. The hydraulic structures are usually treated as internal boundaries of reaches and modeled by algebraic relationships between the flow and pressure variables. To enable the exchange of information among the control system’s components, a communication network is considered in the second layer. Solving challenging problems of heterogeneous devices and communication issues (e.g., network delay, packet loss, energy consumption) is investigated in this thesis by introducing a hybrid network architecture and a dynamic routing design based on Quality of Service (QoS) requirements of control applications. For network routing, a weighted composition of some standard metrics is proposed so that the routing protocol using the composite metric achieves convergence, loop-freeness and path-optimality properties. Through extensive simulation scenarios, different network performance criteria are evaluated. The comparison of simulation results can validate the interest of this composition approach for dynamic routing. Finally, the third layer introduces an optimal reactive control system developed for the regulatory control of large-scale irrigation network under a Distributed Cooperative Model Predictive Control (DCMPC) framework. This part discusses the implementation of different control strategies (e.g., centralized, decentralized, and distributed strategies) and how the cooperative communication among local MPC controllers can be included to improve the performance of the overall system. Managing divergent (or outdated) information exchange among controllers is considered in this thesis as a consensus problem and solved by an asynchronous consensus protocol. This approach based on the multi-agent system paradigm to distributed control requires each controller to agree with its neighbors on some data values needed during action computation. For simulations, a particular benchmark of an irrigation channel is considered. The comparison of simulation results validate the benefits of the distributed cooperative control approach over other control strategies

Internet est un outil formidable pour l'éducation, la communication et la collaboration, mais ses usages majoritaires sont actuellement sous monopole de grandes multinationales (GAFAM), ce qui a des conséquences sur le respect des droits humains et des libertés individuelles. Cette thèse propose des outils pour le développement d'applications décentralisées : des applications sur Internet qui fournissent des fonctionnalités similaires aux plateformes des GAFAM, mais de manière décentralisée, afin de rendre le pouvoir aux utilisateur pour décider démocratiquement de leur fonctionnement et de leurs usages. Nous nous concentrons sur les algorithmes épidémiques qui sont particulièrement adaptés dans le cadre de réseaux ouverts à large échelle. Nous proposons des contributions sur la diffusion causale de messages tolérante aux nœuds Byzantins, la diffusion causale épidémique à l'aide d'un stockage d'événements synchronisé par anti-entropie, l'échantillonnage aléatoire de pairs résistants aux attaques Byzantines et aux attaques Sybil, ainsi qu'un nouvel algorithme épidémique de diffusion totalement ordonnée qui tolère les nœuds malicieux et fournit un débit de messages élevé
The Internet is a formidable tool for education, communication and collaboration, however it is currently being monopolized by large corporations (GAFAM), which has consequences for many social issues such as respect of human rights and individual freedoms. This thesis focuses on ways to build decentralized applications: Internet applications that provide levels of functionality similar to those provided by the GAFAM, but that function in a decentralized manner, empowering the users to democratically decide of their functioning and their uses. We focus on epidemic algorithms, which are particularly suited to the context of very large open networks. We make contributions on causal broadcast in presence of Byzantine nodes, epidemic causal broadcast using an event store synchronized with an anti-entropy algorithm, random peer sampling in presence of Byzantine nodes and Sybil attacks, as well as a new epidemic total order broadcast which is tolerant to malicious nodes and provides high throughput message delivery

Cette thèse adresse le problème du consensus dans les réseaux. On étudie des réseaux composés d'agents identiques capables de communiquer entre eux, qui ont une mémoire et des capacités de calcul. Le réseau ne possède pas de nœud central de fusion. Chaque agent stocke une valeur qui n'est pas initialement connue par les autres agents. L'objectif est d'atteindre le consensus, i.e. tous les agents ont la même valeur, d'une manière distribuée. De plus, seul les agents voisins peuvent communiquer entre eux. Ce problème a une longue et riche histoire. Si toutes les valeurs appartiennent à un espace vectoriel, il existe plusieurs protocoles pour résoudre le problème. Une des solutions connues est l'algorithme du gossip qui atteint le consensus de manière asymptotique. C'est un protocole itératif qui consiste à choisir deux nœuds adjacents à chaque itération et de les moyenner. La spécificité de cette thèse est dans le fait que les données stockées par les agents n'appartiennent pas nécessairement à un espace vectoriel, mais à un espace métrique. Par exemple, chaque agent stocke une direction (l'espace métrique est l'espace projectif) ou une position dans un graphe métrique (l'espace métrique est le graphe sous-jacent). Là, les protocoles de gossip mentionnés plus haut n'ont plus de sens car l'addition qui n'est plus disponibles dans les espaces métriques. Cependant, dans les espaces métriques les points milieu ont du sens dans certains cas. Et là ils peuvent se substituer aux moyennes arithmétiques. Dans ce travail, on a compris que la convergence du gossip avec les points milieu dépend de la courbure. On s'est focalisés sur le cas où l'espace des données appartient à une classe d'espaces métriques appelés les espaces CAT(k). Et on a pu démontrer que si les données initiales sont suffisamment "proches" dans un sens bien précis, alors le gossip avec les points milieu - qu'on a appelé le Random Parwise Midpoints- converge asymptotiquement vers un consensus
This thesis deals with the problem of consensus on networks. Networks under study consists of identical agents that can communicate with each other, have memory and computational capacity. The network has no central node. Each agent stores a value that, initially, is not known by other agents. The goal is to achieve consensus, i.e. all agents having the same value, in a fully distributed way. Hence, only neighboring agents can have direct communication. This problem has a long and fruitful history. If all values belong to some vector space, several protocols are known to solve this problem. A well-known solution is the pairwise gossip protocol that achieves consensus asymptotically. It is an iterative protocol that consists in choosing two adjacent nodes at each iteration and average them. The specificity of this Ph.D. thesis lies in the fact that the data stored by the agents does not necessarily belong to a vector space, but some metric space. For instance, each agent stores a direction (the metric space is the projective space) or position on a sphere (the metric space is a sphere) or even a position on a metric graph (the metric space is the underlying graph). Then the mentioned pairwise gossip protocols makes no sense since averaging implies additions and multiplications that are not available in metric spaces: what is the average of two directions, for instance? However, in metric spaces midpoints sometimes make sense and when they do, they can advantageously replace averages. In this work, we realized that, if one wants midpoints to converge, curvature matters. We focused on the case where the data space belongs to some special class of metric spaces called CAT(k) spaces. And we were able to show that, provided initial data is "close enough" is some precise meaning, midpoints-based gossip algorithm – that we refer to as Random Pairwise Midpoints - does converge to consensus asymptotically. Our generalization allows to treat new cases of data spaces such as positive definite matrices, the rotations group and metamorphic systems

Présentation d'un cadre général pour l'étude et l'analyse des algorithmes répartis et résolution de plusieurs problèmes de fond relatifs à la complexité dans les systèmes répartis. Développement de divers outils d'analyse en moyenne de la complexite en messages de protocoles généraux à consensus. Résolution par l'analyse mathématique d'un problème ouvert sur les performances comparées des anneaux uni et bidirectionnels pour la complexité en moyenne en messages d'algorithmes d'élection déterministes. Un algorithme probabiliste de construction d'un arbre couvrant sur un système distribué anonyme et quelconque est développé. Deux théorèmes sont proposés qui bornent la faille des messages en fonction de la complexite en messages des algorithmes distribués asynchrones du point de vue de la quantité d'information.

Cette thèse considère principalement trois problèmes dans le domaine du contrôle distribué coopératif des systèmes multi-agents(SMA): le consensus, la navigation en formation et le maintien en formation d'un groupe d'agents lorsqu'un agent disparait. Nous proposons 3 algorithmes pour résoudre le problème du calcul distribué d'un consensus à partir de l'approche leadeur-suiveur dans le contexte SMA à dynamique non-linéaire. La référence est définie comme un leader virtuel dont on n'obtient, localement, que les données de position et de vitesse. Pour résoudre le problème du suivi par consensus pour les SMA à dynamique non-linéaire, nous considérons le suivi par consensus pour SMA de premier ordre. On propose des résultats permettant aux suiveurs de suivre le leadeur virtuel en temps fini en ne considérant que les positions des agents. Ensuite, nous considérons le suivi par consensus de SMA de second. Dans le cas de la planification de trajectoire et la commande du mouvement de la formation multi-agents. L'idée est d'amener la formation, dont la dynamique est supposée être en 3D, d'une configuration initiale vers une configuration finale (trouver un chemin faisable en position et orientation) en maintenant sa forme tout le long du chemin en évitant les obstacles. La stratégie proposée se décompose en 3 étapes. Le problème du Closing-Rank se traduit par la réparation d'une formation rigide multi-agents "endommagée" par la perte de l'un de ses agents. Nous proposons 2 algorithmes d'autoréparation systématique pour récupérer la rigidité en cas de perte d'un agent. Ces réparations s'effectuent de manière décentralisée et distribuée n'utilisant que des informations de voisinage.

Ce travail s'inscrit dans le cadre de la commande d'un système multi agents/ multi véhicules. Cette thèse traite en particulier le cas de la commande d'un système multi-robots mobiles non-holonomes. L'objectif est de concevoir des lois de commandes appropriées pour chaque robot de sorte que l'ensemble des robots puisse exécuter des tâches spécifiques, de suivre des trajectoires désirées tout en maintenant des configurations géométriques souhaitées. L'approche leadeur-suiveur pour la commande d'un groupe de robots mobiles non-holonomes est étudiée en intégrant la technologie backstepping, avec une approche basée sur les neurodynamiques bioinspirées. Le problème de commande distribuée d'un système multi robots sur le consensus est également étudié. Des lois de commandes cinématiques distribuées sont développés afin de garantir au système multi-robots la convergence exponentielle vers une configuration géométrique souhaitée. Afin de tenir compte de la dynamique des paramètres inconnus, des commandes adaptatives de couple sont développés pour que le système multi-robots puisse converger asymptotiquement vers le modèle géométrique souhaité. Lorsque la dynamique est inconnue, des commandes à base de réseaux de neurones sont proposées

Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority
This thesis is devoted to the study of stochastic decentralized processes. Typical examples in the real world include the dynamics of weather and temperature, of traffic, the way we meet our friends, etc. We take the rich tool set from probability theoryfor the analysis of Markov Chains and employ it to study a wide range of such distributed processes: Forest Fire Model (social networks), Balls-into-Bins with Deleting Bins, and fundamental consensus dynamics and protocols such as the Voter Model, 2-Choices, and 3-Majority

Les protocoles de consensus ont gagné beaucoup d’intérêt ces dernières années. Dans cette thèse, nous étudions les problèmes d’optimisation, de contrôle, et de théorie de jeu qui se posent dans ces protocoles. Tout d’abord, nous étudions les techniques d’optimisation pour des problèmes de sélection de poids permettant ainsi d’augmenter la vitesse de convergence de protocoles de consensus dans les réseaux. Nous proposons de sélectionner les poids en appliquant un algorithme d’approximation: minimisation de la norme p de Schatten de la matrice de poids. Nous caractérisons l’erreur induite par cette approximation et nous montrons que l’algorithme proposé a l’avantage qu’il peut être soit résolu de façon distribuée. Ensuite, nous proposons un cadre conceptuel d’analyse des jeux d’adversaire qui peut ajouter du bruit aux poids utilisés par l’algorithme de consensus de moyenne afin d’éloigner le système de consensus. Nous analysons également la performance des algorithmes de consensus de moyenne où les informations échangées entre les agents voisins sont soumises à la quantification uniforme déterministe (les valeurs réelles envoyées par les nœuds de leurs voisins sont tronquées). Le problème de la terminaison des protocoles de consensus s’avère difficile dans le cadre distribué. Nous proposons un algorithme distribué pour la terminaison des protocoles de consensus. L’algorithme réduit la charge de communication tout en garantissant la convergence vers un consensus. Enfin, nous proposons une mesure de similarité qui évalue la qualité d’un regroupement (clustering) des nœuds dans un réseau. Un algorithme local de clustering basé sur cette métrique est donné
Consensus protocols have gained a lot of interest in the recent years. In this thesis, we study optimization, control, and game theoretical problems arising in consensus protocols. First, we study optimization techniques for weight selection problems to increase the speed of convergence of discrete-time consensus protocols on networks. We propose to select the weights by applying an approximation algorithm: minimizing the Schatten p-norm of the weight matrix. We characterize the approximation error and we show that the proposed algorithm has the advantage that it can be solved in a totally distributed way. Then we propose a game theoretical framework for an adversary that can add noise to the weights used by averaging protocols to drive the system away from consensus. We give the optimal strategies for the game players (the adversary and the network designer) and we show that a saddle-point equilibrium exists in mixed strategies. We also analyze the performance of distributed averaging algorithms where the information exchanged between neighboring agents is subject to deterministic uniform quantization (e.g., when real values sent by nodes to their neighbors are truncated). Consensus algorithms require that nodes exchange messages persistently to reach asymptotically consensus. We propose a distributed algorithm that reduces the communication overhead while still guaranteeing convergence to consensus. Finally, we propose a score metric that evaluates the quality of clusters such that the faster the random walk mixes in the cluster and the slower it escapes, the higher is the score. A local clustering algorithm based on this metric is proposed

Dans un ordinateur multiprocesseur, lors de l'accès à la mémoire partagée, il faut synchroniser les entités de calcul (processus). Cela peut se faire à l'aide de verrous, mais des problèmes se posent (par exemple interblocages, mauvaise tolérance aux pannes). On s'est intéressé à l'implémentation d'abstractions (consensus et construction universelle) qui peuvent faciliter la programmation concurrente sans attente, sans utiliser de verrous mais basés sur des lectures/écritures atomiques (LEA). L'usage exclusive des LEA ne permet pas de réaliser un consensus sans attente. Néanmoins, autoriser l'usage de primitives offrant une puissance de synchronisation plus forte que des LEA, mais coûteuse en temps de calcul, le permet. Nous nous sommes donc intéressés dans cette thèse à des programmes qui limitent l'usage de ces primitives aux seules situations où les processus sont en concurrence, ces programmes sont dit solo-rapides. Une autre piste étudiée est de permettre à l'objet, lorsqu'il y a de la concurrence, de retourner une réponse spéciale "abandon" qui signifie l'abandon des calculs en cours. Ces objets sont dit abandonnables. D'une part, nous donnons des implémentations d'objets concurrents sans attente, abandonnables et/ou solo-rapides. Pour cela, nous proposons une construction universelle qui assure à l'objet implémenté d'être abandonnable et solo-rapide ; nous avons réalisés des algorithmes de consensus solo-rapides et des algorithmes de consensus abandonnable. D'autre part nous étudions la complexité en espace de ces implémentations en proposant des bornes inférieures sur l'implémentation des objets abandonnables et sur le consensus
In multiprocessor computer, synchronizations between processes are needed for the access to the shared memory. Usually this is done by using locks, but there are some issues as deadlocks or lack of fault-tolerance. We are interested in implementing abstractions (as consensus or universal construction) which ease the programming of wait-free concurrent objects, without using lock but based on atomic Read/Write operations (ARW). Only using the ARW does not permit to implement wait-free consensus. The use of primitives which offer a higher power of synchronization than the ARW is needed. But these primitives are more expensive in computing time. Therefore, we are interested in this thesis in the design of algorithms which restrict the use of these primitives only to the cases where processes are in contention. These algorithms are said solo-fast. Another direction is to allow the object to abort the computation in progress - and to return a special response "abort" - when there is contention. These objects are named abortable. On the one hand we give wait-free, abortable and/or solo-fast concurrent object implementations. Indeed we proposed a universal construction which ensure to the implemented object to be abortable and solo-fast. We have also realized solo-fast consensus algorithms and abortable consensus algorithms. On the other hand, we study the space complexity of these implementations : we prove space lower bound on the implementation of abortable object and consensus

Ce travail s’inscrit dans le cadre de la commande d’un système multi agents/ multi véhicules. Cette thèse traite en particulier le cas de la commande d’un système multi-robots mobiles non-holonomes. L'objectif est de concevoir des lois de commandes appropriées pour chaque robot de sorte que l’ensemble des robots puisse exécuter des tâches spécifiques, de suivre des trajectoires désirées tout en maintenant des configurations géométriques souhaitées. L’approche leadeur-suiveur pour la commande d’un groupe de robots mobiles non-holonomes est étudiée en intégrant la technologie backstepping, avec une approche basée sur les neurodynamiques bioinspirées. Le problème de commande distribuée d’un système multi robots sur le consensus est également étudié. Des lois de commandes cinématiques distribuées sont développés afin de garantir au système multi-robots la convergence exponentielle vers une configuration géométrique souhaitée. Afin de tenir compte de la dynamique des paramètres inconnus, des commandes adaptatives de couple sont développés pour que le système multi-robots puisse converger asymptotiquement vers le modèle géométrique souhaité. Lorsque la dynamique est inconnue, des commandes à base de réseaux de neurones sont proposées
This work is based on the multi-agent system / multi-vehicles. This thesis especially focuses on formation control of multiple nonholonomic mobile robots. The objective is to design suitable controllers for each robot according to different control tasks and different constraint conditions, such that a group of mobile robots can form and maintain a desired geomantic pattern and follow a desired trajectory. The leader-follower formation control for multiple nonholonomic mobile robots is investigated under the backstepping technology, and we incorporate a bioinspired neurodynamics scheme in the robot controllers, which can solve the impractical velocity jumps problem. The distributed formation control problem using consensus-based approach is also investigated. Distributed kinematic controllers are developed, which guarantee that the multi-robots can at least exponentially converge to the desired geometric pattern under the assumption of "perfect velocity tracking". However, in practice, "perfect velocity tracking" doesn’t hold and the dynamics of robots should not be ignored. Next, in consideration of the dynamics of robot with unknown parameters, adaptive torque controllers are developed such that the multi-robots can asymptotically converge to the desired geometric pattern under the proposed distributed kinematic controllers. Furthermore, When the partial knowledge of dynamics is available, an asymptotically stable torque controller has been proposed by using robust adaptive control techniques. When the dynamics of robot is unknown, the neural network controllers with the robust adaptive term are proposed to guarantee robust velocity tracking

L’avènement de composants électroniques compacts et bon marché présage d’une diversification rapide d’applications dans lesquelles des agents autonomes en réseau travaillent à réaliser un objectif commun. Ces tâches complexes, en dépit de leur diversité, dépendent de la maîtrise d’un petit nombre de primitives de coordination, dont l’implémentation programmatique par des agents à faible puissance et capacité calculatoire constitue l’un des enjeux majeurs du développement de telles applications réparties. Parmi ces dernières, citons par exemple la coordination du mouvement de réseaux mobiles et véhiculaires, l’aggrégation et le traitement distribué de mesures relevées par des réseaux de capteurs, et le a répartition de charge en temps réel au sein d’un réseau fournissant un service à grande échelle. L’implémentation distribuée de telles primitives se doit de répondre à différentes contraintes, qui ne résultent pas toutes de la nature numérique des entités constitutives du réseau ; en conséquence, l’étude théorique de ces primitives s’applique à la modélisation de comportements complexes de systèmes étudiés par les sciences naturelles, tels que les mouvements collectifs animaliers ou le système nerveux.Cette monographie traite spécifiquement d’algorithmes distribués qui réalisent le calcul asymptotique de la moyenne de valeurs initialement détenues par les agents d’un réseau dont les liens de communication sont amenés à changer au cours du temps, ceci en l’absence de coordination centralisée. Ces algorithmes doivent être implémentables localement, en n’exploitant que l’information qui peut être collectée par les agents lors de leurs interactions sur le réseau, et en l’absence de mécanisme particulier pour marquer le départ, tel qu’un signal global ou un agent initiateur.Nous développons des algorithmes qui réalisent un tel consensus de moyenne sur des réseaux dynamiques présentant certaines propriétés locales. Ces algorithmes sont simples à décrire, légers à implémenter, et opèrent en temps polynomial en le nombre d’agents.Sur des réseaux présentant des interactions bidirectionnelles, nous fournissons un algorithme déterministe qui réalise le calcul asymptotique de la moyenne dès lors que le réseau ne se sépare jamais de façon permanente. Pour le cas plus général d’interactions asymétriques, nous présentons un algorithme Monte Carlo stabilisant qui est efficace en termes de complexité spatiale et opère en temps linéaire. Ce dernier algorithme admet une extension dont les exécutions terminent en tolérant un départ asynchrone des agents. Nos algorithmes sont à considérer en regard de résultats et de méthodes qui reposent sur une information globale fournie externalement aux agents, sur des hypothèses de brisure initiale de symétrie, ou qui exploitent une topologie particulière et ne se généralisent pas à des réseaux quelconques. Dans ce contexte, nous contribuons des algorithmes dont les conditions de validité sont purement locales dans le temps et l’espace : pour le modèle d’interactions bidirectionnelles, nous montrons que le calcul asymptotique de la moyenne est réalisable par des agents déterministes, là où pour le modèle général nous fournissons des algorithmes randomisés dont les performances asymptotiques sont bien meilleures que celles de protocoles à information complète et robustes aux départs asynchrones.Par-delà l’intérêt immédiat à l’obtention d’algorithmes efficaces implémentables, notre étude s’inscrit dans un effort de cartographie des limites que la localité des interactions impose aux applications réparties
Compact and cheap electronic components announce the near-future development of applications in which networked systems of autonomous agents are made to carry over complex tasks. These, in turn, depend on a small number of coordination primitives, which need to be programmatically implemented into potentially low-powered, and computationally limited, agents.Such applications include for example the coordination of the collective motion of mobile and vehicular networks, the distributed aggregation and processing of data measured locally in sensor networks, and the on-line repartition of processing load in the computer farms powering wide-scale services. As they address constraints that are not specific to the digital nature of the network such primitives also serve to model complex behavior of natural systems, such as flocks and neural networks.This monograph focuses on providing distributed algorithms that asymptotically compute the average of initial values, initially present at each agent of a networked system with time-varying communication links and in the absence of centralized control. Additionally, we consider the weaker problem of getting the agents to asymptotically agree on any value within the initial bounds. We focus on locally implementable algorithms, which leverage no information beyond what the agents can acquire by themselves, and which need no bootstrapping mechanism like a global start signal or a leader agent.We provide distributed average consensus algorithms that operate over dynamic networks given different local assumptions. These algorithms are computationally simple and operate in polynomial time in the number of agents.For bidirectional communications, we give a deterministic algorithm which asymptotically computes the average as long as the network never becomes permanently disconnected. For the general case of asymmetric communications, we provide a stabilizing Monte Carlo algorithm that is efficient in bandwidth and memory and operates in linear time, along with an extension by which the algorithm can be made to uniformly terminate over any connected network in which agents may start asynchronously.This contrasts with a plethora of results and techniques in which agents are provided external information – the size of the system, a bound over their degree, – helped with exogenous symmetry breaking – a leader agent, unique identifiers, – or where the network is expected to conform to a specific shape – a ring, a a complete network, a regular graph. Indeed, because very different networks may look alike to the agents, they are limited in what they can learn locally, and many functions are impossible to compute in a fully distributed manner without assuming some structure in the network or additional symmetry-breaking device. Given these stringent constraints, our contribution is to offer algorithms whose validity depends uniquely on local and instantaneous conditions. In the bidirectional model, we show that anonymous deterministic agents can asymptotically compute the average in polynomial time. For the general model of directed interactions, we allow agents to consult random oracles. Under those conditions, full information protocols are capable of solving any problem, and so we focus on the spatial complexity and tolerance to a lack of initial coordination in the agents, while offering stronger termination guarantees than in the bidirectional case. Beyond the fact that locally implementable algorithms are eminently desirable, our study contributes to mapping the limits that local interactions impose on networks

Avec l’arrivée massive des technologies sans fil, le nombre de terminaux mobiles n’a cessé de croître, pour des usages et des ressources de communication diversifiés. En intégrant les objets du quotidien, nos réseaux de communications sont devenus dynamiques aussi bien en termes de ressources que de topologie physique, offrant accès à des informations de plus en plus riches. La tâche de gestion s’est ainsi complexifiée et requiert des temps de réponse de plus en plus courts difficilement réalisables par un administrateur humain. Il devient indispensable de mettre en œuvre des capacités de gestion autonomes pour les nouveaux réseaux. Dans tous les cas, la gestion d’un système implique une étape essentielle : sa mesure et sa supervision. Peu importe sa nature, c’est cette étape de prise d’information qui permet sa caractérisation, son analyse et son contrôle. Le domaine des réseaux n’échappe pas à cette règle et les objets qui le composent auront besoin d’acquérir des informations sur leur environnement pour mieux s’y adapter. Dans cette thèse, nous nous intéressons au partage efficace de ces informations de mesures à des fins d’auto-analyse et d’évaluation distribuée de la performance. Après avoir formalisé le problème de la mesure distribuée, nous nous consacrons dans un premier temps à l’organisation des échanges de mesures dans les graphes dynamiques. Nous proposons une nouvelle heuristique pour le consensus de la moyenne qui converge plus rapidement que celles de l’état de l’art. Dans un second temps, nous considérons des topologies plus stables pouvant utiliser des flux TCP comme moyen d’échange. Nous proposons un mécanisme d’ordonnancement de ces flux qui conserve le même comportement face à la congestion, tout en réduisant leur latence moyenne. Enfin, nous nous intéressons à l’information de mesure échangée. Nous montrons comment les nœuds peuvent superviser diverses métriques telles que la performance d’un système en se basant sur l’utilité de ses agents, et proposons une méthode pour qu’ils puissent analyser l’évolution de cette performance
With the massive rise of wireless technologies, the number of mobile stations is constantly growing. Both their uses and their communication resources are diversified. By integrating our daily life objects, our communication networks become dynamic in terms of physical topology but also in term of resources. Furthermore, they give access to a richer information. As a result, the management task has become complex and requires shorter response time that a human administrator can not respect. It becomes necessary to develop an autonomic management behavior in next generation networks. In any manner, managing a system requires essential steps which are : its measurement and its supervision. Whatever the nature of a system, this stage of information gathering, allows its characterization and its control. The field of networks is not the exception to the rule and objects that compose them will need to acquire information on their environment for a better adaptation. In this thesis, we focus on the efficient sharing of this information, for self-analysis and distributed performance evaluation purposes. After having formalized the problem of the distributed measurement, we address in a first part the fusion and the diffusion of measures in dynamic graphs. We develop a new heuristic for the average consensus problem offering a better contraction rate than the ones of the state of the art. In a second part, we consider more stable topologies where TCP is used to convey measures. We offer a scheduling mechanism for TCP flows that guaranty the same impact on the network congestion, while reducing the average latency. Finally, we show how nodes can supervise various metrics such as the system performance based on their utilities and suggest a method to allow them to analyze the evolution of this performance

Le but de cette thèse concernait l'application des problèmes d'accord au domaine de la tolérance aux défaillances dans les systèmes distribués asynchrones. Pour cela, nous avons tout d'abord exploré de nombreuses voies théoriques concernant le plus fondamental des problèmes d'accord, à savoir le problème du consensus. Cela nous a permis d'établir une hiérarchie des problèmes distribués reposant sur la difficulté à les résoudre en présence de pannes. Puis nous avons mis au point un algorithme probabiliste et général pour le problème du consensus. Cela nous a permis de concevoir une plateforme de tolérance aux défaillances reposant sur deux librairies. D'une part une librairie appelée Eva et conçu de façon à faciliter le développement d'applications distribuées, et d'autre part une librairie appelée Adam reposant sur la première librairie et qui fournit un ensemble de fonctionnalités pour la mise au point de services dupliqués et tolérants les pannes.

Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les nœuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse s’est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil.Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseau
Distributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks.This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network

Durant les dernières années, la taille des systèmes ainsi que leur complexité ont pas mal évolué, entrainant le besoin d'approches distribuées pour la commande et l'aide à la décision. Cette thèse porte sur la résolution d'un problème incluant une commande distribuée et une aide à la décision, l'allocation dynamique de ressource dans un réseau.Pour résoudre ce problème, nous avons étudié un algorithme basé sur un consensus qui ne nécessite pas de calcul centralisé, et qui soit capable de traiter des applications modélisées par des systèmes dynamiques ou par des fonctions sans mémoires. La principale contribution de ce travail de thèse est d'avoir prouvé, en utilisant des outils issus de la théorie des graphes etl'analyse de la passivité, que le contrôleur atteint la solution optimale de façon asymptotique, sans obligation d'avoir une information complète.Afin d'illustrer la pertinence de notre résultat principal, plusieurs applications en ingénierie ont été étudiées, incluant la commande distribuée pour l'économie d'énergie dans des bâtiments intelligents, la gestion des clients dans un environnement de "smart grids", et le développement d'une méthode exacte d'optimisation distribuée pour un problème d'allocation de ressources soumis à des contraintes sur les bornes inférieures.Enfin, nous étudions les techniques d'allocation de ressources basées sur les modèlesde dynamique de populations. Pour les rendre distribuées, nous introduisons le concept dedynamique de populations "pas bien mélangées". Nous montrons que ces dynamiques peuventêtre utilisées pour des structures d'informations contraintes. Même si les dynamiquesde populations "pas bien mélangées" utilisent des informations partielles, ellesconservent des propriétés similaires aux dynamiques classiques qui utilisent desinformations complètes. Plus spécifiquement, la conservation de masse et la convergencevers l'équilibre de Nash sont prouvées
Since the complexity and scale of systems have been growing in the last years, distributed approaches for control and decision making are becoming more prevalent. This dissertation focuses on an important problem involving distributed control and decision making, the dynamic resource allocation in a network. To address this problem, we explore a consensus--based algorithm that does not require any centralized computation, and that is capable to deal with applications modeled either by dynamical systems or by memoryless functions. The main contribution of our research is to prove, by means of graph theoretical tools and passivity analysis, that the proposed controller asymptotically reaches an optimal solution without the need of full information. In order to illustrate the relevance of our main result, we address several engineering applications including: distributed control for energy saving in smart buildings, management of the customers of an aggregating entity in a smart grid environment, and development of an exact distributed optimization method that deals with resource allocation problems subject to lower--bound constraints. Finally, we explore resource allocation techniques based on classic population dynamics models. In order to make them distributed, we introduce the concept of non--well--mixed population dynamics. We show that these dynamics are capable to deal with constrained information structures that are characterized by non--complete graphs. Although the proposed non--well--mixed population dynamics use partial information, they preserve similar properties of their classic counterpart, which uses full information. Specifically, we prove mass conservation and convergence to Nash equilibrium
Dado que la complejidad y la escala de los sistemas sehan ido incrementando en los últimos años, las técnicas centralizadas de control y toma de decisiones están siendo reemplazadas por métodos distribuidos. Esta tesis se centra en un importante problema que involucra control y toma de decisiones distribuidas: la asignación dinámica de recursos en redes. Para abordar este problema, exploramos un algoritmo basado en consenso que no requiere computación centralizada, y que puede ser usado en aplicaciones modeladas ya sea por sistemas dinámicos o funciones sin memoria. La principal contribución de esta tesis es probar, por medio de teoría de grafos y pasividad, que el algoritmo propuesto alcanza asintóticamente una solución óptima sin la necesidad de usar información completa. Para ilustrar la relevancia del resultado principal de esta disertación, abordamos varias aplicaciones en ingeniería,incluyendo: el control distribuido en edificios inteligentes orientado a la eficiencia energética, la gestión de los clientes de un agregador en una red inteligente en la que se aplican estrategias de respuesta de la demanda, y el desarrollo de un método de optimización exacto que permite incluir restricciones de límite inferior. Finalmente, se exploran otras técnicas de asignación derecursos inspiradas en modelos de dinámicas poblacionales. Se introduce el concepto de poblaciones no—bien—mezcladas, y se muestra que las dinámicas asociadas a este tipo de poblaciones cuentan con una estructura de información local, caracterizada por grafos que no son completos. A pesar de que las dinámicas propuestas usan información parcial, ellas preservan características similares a las dinámicas poblacionales clásicas que usan información completa

Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps. L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes. Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le k-accord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle. De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle
Dynamic systems are distributed systems in which (1) processes can join or leave the system during the run, and (2) the communication graph evolves over time. The failure detector abstraction was introduced as a way to circumvent the impossibility of solving consensus in asynchronous systems prone to crash failures. A failure detector is a local oracle that provides processes in the system with unreliable information on process failures. But a failure detector that is sufficient to solve a given problem in a static system is not necessarily sufficient to solve the same problem in a dynamic system. Additionally, some existing failure detectors cannot be implemented in dynamic systems. Therefore, it is necessary to redefine existing failure detectors and provide new algorithms. In this thesis, we provide a new definition of a failure detector for k-set agreement, and prove that it is sufficient to solve k-set agreement in dynamic systems. We also design a dynamic system model and an algorithm that implements this new failure detector. Additionally, we adapt an existing failure detector for mutual exclusion and prove that it is still the weakest failure detector to solve mutual exclusion in dynamic systems, which means that it is weaker than any other failure detector capable of solving mutual exclusion

L'évolution technique des "objets communicants" tels que les ordinateurs portables, les assistants personnels, etc..., confirme l'intérêt porté aux technologies "sans fil". Le développement rapide des protocoles de communication sans fil (Bluetooth, WIFI, ...) a permis la généralisation de nouveaux "réseaux locaux ad-hoc" principalement caractérisés par leur topologie dynamique et l'hétérogénéité de leurs composants. Aussi, les infrastructures logicielles reposant sur de tels environnements doivent pouvoir s'adapter et gérer cette dynamicité (connexions/déconnexions fréquentes ainsi que la forte variabilité des communications. Dans ce contexte, l'objectif général est de concevoir des algorithmes permettant de maintenir la cohérence d'un groupe d'entités hétérogènes partageant des services sur des architectures fortement instables. La problématique concerne donc la prise de décision en environnement distribué en considérant les particularités du réseau sous-jacent. Dans cette thèse, nous proposons une méthodologie d'approche concernant la caractérisation des performances envisageables dans un environnement totalement distribué s'appuyant sur un protocole de communication sans fil. Cette approche consiste également en l'identification des différentes perturbations susceptibles d'interférer dans le bon déroulement des applications. Par ailleurs, un algorithme de consensus adapté aux spécificités de l'environnement et basé sur un principe d'interaction avec un mécanisme de détection de défaillances a été développé et implanté. Afin de valider cette approche algorithmique, diverses expérimentations et évaluations qualitatives et quantitatives ont été réalisées.

Ces dernières années, l’émergence des nouvelles technologies tels que la miniaturisation des composants, les dispositifs de communication sans fils, l’augmentation de la taille de stockage et les capacités de calcul, a permis la conception de systèmes multi-agents coopératifs de plus en plus complexes. L’un des plus grands axes de recherche dans cette thématique concerne la commande en formation de flottes de véhicules autonomes. Un grand nombre d’applications et de missions, civiles et militaires, telles que l’exploration, la surveillance, et la maintenance, ont alors été développées et réalisées dans des milieux variés (terre, air, eau). Durant l’exécution de ces tâches, les véhicules doivent interagir avec leur environnement et entre eux pour se coordonner. Les outils de communication disponibles disposent souvent d’une portée limitée. La préservation de la connexion au sein du groupe devient alors un des objectifs à satisfaire pour que la tâche puisse être accomplie avec succès. Une des possibilités pour garantir cette contrainte est le déplacement en formation permettant de préserver les distances et la structure géométrique du groupe. Il est toutefois nécessaire de disposer d’outils et de méthodes d’analyse et de commande de ces types de systèmes afin d’exploiter au maximum leurs potentiels. Cette thèse s’inscrit dans cette direction de recherche en présentant une synthèse et une analyse des systèmes dynamiques multi-agents et plus particulièrement la commande en formation de véhicules autonomes. Les lois de commande développées dans la littérature pour la commande en formation permettent d’accomplir un grand nombre de missions avec un niveau de performance élevé. Toutefois, si un défaut/défaillant apparaît dans la formation, ces lois de commandes peuvent s’avérer très limitées, engendrant un comportement instable du système. Le développement de commandes tolérantes aux défauts devient alors primordial pour maintenir les performances de commande en présence de défauts. Cette problématique sera traitée dans ce mémoire de thèse et concernera le développement et la conception de commandes en formation tolérantes au défaut dévolu à une flotte de véhicules autonomes suivant différente configuration/structuration
In recent years, the emergence of new technologies such as miniaturization of components, wireless communication devices, increased storage size and computing capabilities have allowed the design of increasingly complex cooperative multi-agent systems. One of the main research axes in this topic concerns the formation control of fleets of autonomous vehicles. Many applications and missions, civilian and military, such as exploration, surveillance, and maintenance, were developed and carried out in various environments. During the execution of these tasks, the vehicles must interact with their environment and among themselves to coordinate. The available communication tools are often limited in scope. The preservation of the connection within the group then becomes one of the objectives to be satisfied in order to carry out the task successfully. One of the possibilities to guarantee this constraint is the training displacement, which makes it possible to preserve the distances and the geometrical structure of the group. However, it is necessary to have tools and methods for analyzing and controlling these types of systems in order to make the most of their potential. This thesis is part of this research direction by presenting a synthesis and analysis of multi-agent dynamical systems and more particularly the formation control of autonomous vehicles. The control laws developed in the literature for formation control allow to carry out a large number of missions with a high level of performance. However, if a fault/failure occurs in the training, these control laws can be very limited, resulting in unstable system behavior. The development of fault tolerant controls becomes paramount to maintaining control performance in the presence of faults. This problem will be dealt with in more detail in this thesis and will concern the development and design of Fault tolerant controls devolved to a fleet of autonomous vehicles according to different configuration/structuring

Les blockchains (ou chaîne de blocs) font partie des technologies les plus attrayantes, autant dans le domaine scientifique que pour le grand public. Une blockchain est un registre distribué dont l’objectif est de garantir de la transparence, de l’intégrité des données et d’autres avantages par rapport aux registres centralisés. La technologie blockchain a été révélée et est devenue populaire grâce à l’avènement de la cybermonnaie Bitcoin. Depuis 2008 et la création de Bitcoin, les blockchains sont devenue extrêmement populaires, avec un intérêt à son pic en 2017. Les blockchains sont quasiment une technologie “à la mode”: il existe un observatoire de la blockchain initié par la Commission Européenne, des événements blockchains dans plusieurs pays, etc. La plupart des blockchains ont comme application la finance, mais les propriétés qu’elles promettent sont intéressantes et utiles pour bien des domaines (ex : médecine, notariat, etc.). Malgré les promesses et intérêts, afin d’espérer une meilleure adoption, il est nécessaire de s'assurer que la technologie est viable du point de vue environnemental, que les garanties promises sont satisfaites, qu'elle puisse être utilisée dans les environnements réels, etc. Dans cette thèse, nous définissons le problème résolu par les blockchains à comité ainsi que leur équité ; cela a permis de corriger une des blockchains les plus utilisées. Notre second apport majeur est une méthodologie permettant d’étudier le comportement des participants dans les blockchains. Grâce à cela, nous montrons les conditions nécessaires où le comportement rationnel des participants mène à des situations où les propriétés des blockchains sont satisfaites
Blockchains are one of the most appealing technologies over the last years, both for scientists and for the general public. Blockchains are distributed ledgers that aim to offer transparency, integrity and many more advantages over their centralised counterparts. Blockchains were “revealed” and became popular thanks to the creation and rise of the cryptocurrency Bitcoin. Over the years, blockchain technologies become more and more popular with an exceptional peak in 2017. Blockchains are becoming mainstream technologies, as there is an observatory for blockchains established by the European Commission, blockchain forums in many countries, blockchain start-ups are flourishing, scientific conferences are discussing the topic, and even some scientific conferences are now specifically dedicated to the technology, etc. The blockchain technology promises, thanks to its integrity and transparency properties to be useful and interesting in various domains, and not only for financial systems. However, many questions and doubts float around it. Is it environmentally viable? Is the technology even ensuring its promises? Can they be used in real-life settings, etc. In this thesis, using the lens of distributed systems, we study and define the properties of committee-based blockchains and their fairness; that definition allows formalising and helping correct one of the most used blockchain of that class. Furthermore, adding lenses from game theory, we propose a methodology to analyse the rational behaviours of participants in a blockchains system. Using that methodology, we show, under different mechanisms of rewards, the necessary conditions needed to ensure the blockchain properties

Au cours des dernières années, le réseau électrique connait une transformation rapide avec la pénétration massive des unités de production renouvelables et distribuées. Le concept de microgrids (micro-réseau électrique) est un élément clés de cette transition énergétique. Ces micro-réseaux sont constitués par un ensemble de plusieurs unités de production distribuées (DGUs), d'unités de stockage (SUs) et de charges interconnectées par des lignes électriques. Un microgrid peut être installé dans plusieurs endroits, par exemple dans des maisons, des hôpitaux, des quartiers, etc. et fonctionne soit en mode connecté au réseau principale, soit en mode isolé (autonome). Les microgrids sont confrontés à plusieurs défis liés à la garantie de la stabilité, la cybersécurité, l'optimisation des coûts énergétiques, la gestion de l'énergie, la qualité de l'énergie, etc. Dans ce travail, nous concentrons notre attention sur le contrôle des microgrids à courant continu en mode de fonctionnement autonome. La principale contribution de cette thèse est l’établissement de lois de commande par retour d’état distribuées assurant un partage de courant proportionnel entre les unités de production, une régulation de la tension moyenne des lignes et un équilibrage simultané des états de charge des éléments de stockage. En partant de l'hypothèse que les agents (DGU ou SU) ont les mêmes paramètres physiques, la preuve de la convergence exponentielle et globale est donnée en l’absence d’une connaissance de la charge présente sur le réseau. La thèse est divisée en trois parties. La première partie présente le concept des microgrids, un état de l’art sur leurs stratégies de contrôle et les préliminaires mathématiques nécessaires tout au long du manuscrit. La deuxième partie constitue la contribution théorique de cette thèse et aborde la synthèse de lois de contrôle distribuées, garantissant les objectifs envisagés en l’absence d’une connaissance de la charge variable sur le réseau et même en cas de perturbation constantes au niveau de l’entrée de commande. Cette garantie est apportée en considérant trois actions intégrales distribuées de type consensus. Dans la troisième partie, les contrôleurs proposés sont évalués dans différents scénarios par le biais de simulation Matlab/Simulink et de tests Hardware-in-the-Loop (HIL) en temps réel. Les résultats montrent que les objectifs de contrôle sont atteints avec succès, ce qui illustre l'efficacité de la méthodologie de contrôle proposée
In recent years, the power grid has undergone a rapid transformation with the massive penetration of renewable and distributed generation units. The concept of microgrids is a key element of this energy transition. Microgrids are made up of a set of several distributed generation units (DGUs), storage units (SUs) and loads interconnected by power lines. A microgrid can be installed in several locations, for example in houses, hospitals, a neighborhood or village, etc., and operates either in connected mode to the main grid or in isolated (autonomous) mode. Microgrids are facing several challenges related to stability assurance, cyber-security, energy cost optimization, energy management, power quality, etc. In this work, we focus our attention on the control of islanded direct current microgrids. The main contribution is the design of a new distributed control approach to provably achieve current sharing, average voltage regulation and state-of-charge balancing simultaneously with global exponential convergence. The main tools are consensus in multi-agent systems, passivity, Lyapunov stability, linear matrix inequalities, etc. The thesis is divided into three parts. The First part presents the concept of microgrids, a literature review of their control strategies and the mathematical preliminaries required throughout the manuscript. The second part deals with the design of the proposed distributed control approach to achieve the considered objectives. The system is augmented with three distributed consensus-like integral actions, and a distributed-based static state feedback control architecture is proposed. Starting from the assumption that the agents (DGUs or SUs) have the same physical parameters, we provide proof of global exponential convergence. Moreover, the proposed control approach is distributed, i.e., each agent exchange relative information with only its neighbors through sparse communication networks. The proposed controllers do not need any information about the parameters of the power lines neither the topology of the microgrid. The control objectives are reached despite the unknown load variation and constant disturbances. In the third part, the proposed distributed controllers are assessed in different scenarios through Matlab/Simulink simulation and real-time Hardware-in-the-Loop experiment. The results show that the control objectives are successfully achieved, illustrating the effectiveness of the proposed control methodology

Ce travail s’inscrit dans le cadre de la commande d’un système multi agents/ multi véhicules. Cette thèse traite en particulier le cas de la commande d’un système multi-robots mobiles non-holonomes. L'objectif est de concevoir des lois de commandes appropriées pour chaque robot de sorte que l’ensemble des robots puisse exécuter des tâches spécifiques, de suivre des trajectoires désirées tout en maintenant des configurations géométriques souhaitées. L’approche leadeur-suiveur pour la commande d’un groupe de robots mobiles non-holonomes est étudiée en intégrant la technologie backstepping, avec une approche basée sur les neurodynamiques bioinspirées. Le problème de commande distribuée d’un système multi robots sur le consensus est également étudié. Des lois de commandes cinématiques distribuées sont développés afin de garantir au système multi-robots la convergence exponentielle vers une configuration géométrique souhaitée. Afin de tenir compte de la dynamique des paramètres inconnus, des commandes adaptatives de couple sont développés pour que le système multi-robots puisse converger asymptotiquement vers le modèle géométrique souhaité. Lorsque la dynamique est inconnue, des commandes à base de réseaux de neurones sont proposées
This work is based on the multi-agent system / multi-vehicles. This thesis especially focuses on formation control of multiple nonholonomic mobile robots. The objective is to design suitable controllers for each robot according to different control tasks and different constraint conditions, such that a group of mobile robots can form and maintain a desired geomantic pattern and follow a desired trajectory. The leader-follower formation control for multiple nonholonomic mobile robots is investigated under the backstepping technology, and we incorporate a bioinspired neurodynamics scheme in the robot controllers, which can solve the impractical velocity jumps problem. The distributed formation control problem using consensus-based approach is also investigated. Distributed kinematic controllers are developed, which guarantee that the multi-robots can at least exponentially converge to the desired geometric pattern under the assumption of "perfect velocity tracking". However, in practice, "perfect velocity tracking" doesn’t hold and the dynamics of robots should not be ignored. Next, in consideration of the dynamics of robot with unknown parameters, adaptive torque controllers are developed such that the multi-robots can asymptotically converge to the desired geometric pattern under the proposed distributed kinematic controllers. Furthermore, When the partial knowledge of dynamics is available, an asymptotically stable torque controller has been proposed by using robust adaptive control techniques. When the dynamics of robot is unknown, the neural network controllers with the robust adaptive term are proposed to guarantee robust velocity tracking