Du fait du manque de capteurs fiables et bon marché, la problématique de la reconstruction d'état est cruciale pour les bioprocédés, particulièrement pour les (bio)réacteurs à paramètres répartis. C'est pourquoi il est essentiel d'étudier leurs propriétés d'observabilité, qui peuvent notamment dépendre des dimensions spatiales des capteurs. Dans cette thèse, on étudie tout d'abord l'observabilité d'une classe de réacteurs tubulaires à lit fixe mettant en oeuvre une seule réaction biochimique, où un substrat est dégradé suivant une cinétique non linéaire. Plus précisément, l'analyse porte sur un modèle linéarisé, consistant notamment en une Équation aux Dérivées Partielles (EDP) parabolique linéaire comportant un coefficient non uniforme (c.-à-d. dépendant de la variable spatiale). Ce modèle entre dans le cadre d'une classe particulière de systèmes : les systèmes de Sturm-Liouville. Il s'en déduit que tout nombre fini de modes dominants du système est observable par un capteur (de concentration en substrat) situé en sortie et de largeur suffisamment petite. En outre, considérant un minorant et un majorant du coefficient non uniforme, on détermine une expression numérique, fonction du nombre de modes à observer, qui minore cette largeur. La pertinence de ce résultat est confirmée par un exemple numérique : un biofiltre de dénitrification. Cette étude est étendue à un procédé-pilote de digestion anaérobie de l'INRA-Narbonne. On montre l'existence d'un état d'équilibre, autour duquel le comportement du système est modélisé par deux EDP linéaires, dont une à coefficient non uniforme. La démarche précédente est généralisée et on calcule des expressions des largeurs de deux capteurs en fonction du nombre de modes dont on veut s'assurer qu'ils sont observables. Ce résultat s'applique notamment à la conception d'un estimateur d'état.

A reactive control system is a computer system reacting to certain stimuli emitted by its environment in order to maintain it in a desired state. Distributed reactive control systems are generally composed of several processes, running in parallel on one or more computers, communicating with one another to perform the required control task. By their very nature, distributed reactive control systems are hard to design. Their distributed nature and/or the communication scheme used can introduce subtle unforeseen behaviours. When dealing with critical applications, such as plane control systems, or traffic light control systems, those unintended behaviours can have disastrous consequences. It is therefore essential, for the designer, to ensure that this does not happen. For that purpose, rigorous and systematic techniques can (and should) be applied as early as possible in the development process. In that spirit, this work aims at providing the designer with the necessary tools in order to facilitate the development and validation of such distributed reactive control systems. In particular, we show how using a dedicated language called dSL (Distributed Supervision language) can be used to ease the development process. We also study how validations techniques such as model-checking and testing can be applied in this context. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans les systèmes répartis asynchrones, l'horloge logique et le vecteur d'horloges sont deux outils fondamentaux pour gérer la communication et le partage de données entre les entités constitutives de ces systèmes. L'objectif de cette thèse est d'exploiter ces outils avec une perspective d'implantation. Dans une première partie, nous nous concentrons sur la communication de données et contribuons au domaine de la diffusion uniforme à ordre total. Nous proposons le protocole des trains : des jetons (appelés trains) circulent en parallèle entre les processus participants répartis sur un anneau virtuel. Chaque train est équipé d'une horloge logique utilisée pour retrouver les train(s) perdu(s) en cas de défaillance de processus. Nous prouvons que le protocole des trains est un protocole de diffusion uniforme à ordre total. Puis, nous créons une nouvelle métrique : le rendement en termes de débit. Cette métrique nous permet de montrer que le protocole des trains a un rendement supérieur au meilleur, en termes de débit, des protocoles présentés dans la littérature. Par ailleurs, cette métrique fournit une limite théorique du débit maximum atteignable en implantant un protocole de diffusion donné. Il est ainsi possible d'évaluer la qualité d'une implantation de protocole. Les performances en termes de débit du protocole des trains, notamment pour les messages de petites tailles, en font un candidat remarquable pour le partage de données entre coeurs d'un même processeur. De plus, sa sobriété en termes de surcoût réseau en font un candidat privilégié pour la réplication de données entre serveurs dans le cloud. Une partie de ces travaux a été implantée dans un système de contrôle-commande et de supervision déployé sur plusieurs dizaines de sites industriels. Dans une seconde partie, nous nous concentrons sur le partage de données et contribuons au domaine de la RFID. Nous proposons une mémoire répartie partagée basée sur des étiquettes RFID. Cette mémoire permet de s'affranchir d'un réseau informatique global. Pour ce faire, elle s'appuie sur des vecteurs d'horloges et exploite le réseau formé par les utilisateurs mobiles de l'application répartie. Ainsi, ces derniers peuvent lire le contenu d'étiquettes RFID distantes. Notre mémoire répartie partagée à base de RFID apporte une alternative aux trois architectures à base de RFID disponibles dans la littérature. Notre mémoire répartie partagée a été implantée dans un jeu pervasif qui a été expérimenté par un millier de personnes. / In asynchronous distributed systems, logical clock and vector clocks are two core tools to manage data communication and data sharing between entities of these systems. The goal of this PhD thesis is to exploit these tools with a coding viewpoint. In the first part of this thesis, we focus on data communication and contribute to the total order broadcast domain. We propose trains protocol: Tokens (called trains) rotate in parallel between participating processes distributed on a virtual ring. Each train contains a logical clock to recover lost train(s) in case of process(es) failure. We prove that trains protocol is a uniform and totally ordered broadcast protocol. Afterwards, we create a new metric: the throughput efficiency. With this metric, we are able to prove that, from a throughput point of view, trains protocol performs better than protocols presented in literature. Moreover, this metric gives the maximal theoretical throughput which can be reached when coding a given protocol. Thus, it is possible to evaluate the quality of the coding of a protocol. Thanks to its throughput performances, in particular for small messages, trains protocol is a remarkable candidate for data sharing between the cores of a processor. Moreover, thanks to its temperance concerning network usage, it can be worthwhile for data replication between servers in the cloud. Part of this work was implemented inside a control-command and supervision system deployed among several dozens of industrial sites. In the second part of this thesis, we focus on data sharing and contribute to RFID domain. We propose a distributed shared memory based on RFID tags. Thanks to this memory, we can avoid installing a computerized global network. This is possible because this memory uses vector clocks and relies on the network made by the mobile users of the distributed application. Thus, the users are able to read the contents of remote RFID tags. Our RFID-based distributed shared memory is an alternative to the three RFID-based architectures available in the literature. This distributed shared memory was implemented in a pervasive game tested by one thousand users.

Ce travail est consacré à la problématique du suivi des systèmes répartis temps réel. Plus précisément, il se concentre sur les aspects formels de la supervision basée sur des modèles ainsi que sur les problèmes qui lui sont liés. Dans la première partie du travail, nous présentons les propriétés de base de deux modèles formels bien connus utilisés pour la modélisation de systèmes répartis : les réseaux d'automates temporisés et les réseaux de Petri temporels. Nous montrons que le comportement de ces modèles peut être représenté par les procédés dits de branchement. Nous introduisons également les éléments conceptuels clés du système de surveillance. La deuxième partie du travail est consacrée à la question des dépliages avec contraintes qui permettent le suivi des relations causales entre les événements dans un système réparti. Ce type de structure peut reproduire des processus sur la base d'un ensemble totalement non-ordonné d'évènements. Dans notre travail, nous soulevons les problèmes des contraintes de temps et de leurs paramétrages. Les méthodes proposées sont illustrées par des études de cas. La troisième partie du travail traite de la problématique des boucles inobservables qui peuvent résulter de comportements cycliques inobservables des systèmes considérés. Ce type de comportement conduit à un nombre infini d'événements dans les dépliages avec contraintes. La quatrième et dernière partie du travail est consacrée à l'implémentation des méthodes décrites précédemment. / This work is devoted to the issue of monitoring of distributed real-time systems. In particular, it focuses on formal aspects of model-based supervision and problems which are related to it. In its first part, we present the basic properties of two well-known formal models used to model distributed systems: networks of timed automata and time Petri nets. We show that the behavior of these models can be represented with so-called branching processes. We also introduce the key conceptual elements of the supervisory system. The second part of the work is dedicated to the issue of constrained unfoldings which enable us to track causal relationships between events in a distributed system. This type of structure can be used to reproduce processes of the system on the basis of a completely unordered set of previously observed events. Moreover, we show that time constraints imposed on a system and observations submitted to the supervisory system can significantly affect a course of events in the system. We also raise the issue of parameters in time constraints. The proposed methods are illustrated with case studies. The third part of the work deals with the issue of unobservable cyclical behaviors in distributed systems. This type of behaviors leads to an infinite number of events in constrained unfoldings. We explain how we can obtain a finite structure that stores information about all observed events in the system, even if this involves processes that are infinite due to such unobservable loops. The fourth and final part of the work is dedicated to implementation issues of the previously described methods.

L'accroissement régulier de la fréquence des micro-processeurs et des importants gains de puissance qui en avaient résulté ont pris fin en 2005. Les autres techniques matérielles d'amélioration de performance se sont largement essouflées. Les fabricants de micro-processeurs ont donc choisi d'exploiter le nombre croissant de transistors disponibles en plaçant plusieurs cœurs de processeurs sur une même puce. Dans cette thèse, nous préparons l'arrivée de processeurs multi-cœur à grand nombre de cœurs par des recherches dans trois directions. Premièrement, nous améliorons l'environnement de parallélisation CAPSULE (parallélisation conditionnelle) en lui adjoignant des primitives de synchronization de tâches robustes. Nous montrons les gains obtenus par rapport aux approches usuelles en terme de rapidité et de stabilité du temps d'exécution. Deuxièmement, nous adaptons CAPSULE à des machines à mémoire distribuée en présentant un modèle de données qui permet au système de déplacer automatiquement les données en fonction des accès effectués par les programmes. De nouveaux algorithmes répartis et locaux permettent de décider de la création effective des tâches et de leur répartition. Troisièmement, nous développons un nouveau simulateur d'évènements discrets, SiMany, qui peut prendre en charge des centaines à des milliers de cœurs. Il est plus de 100 fois plus rapide que les meilleurs simulateurs flexibles actuels. Après validation, nous montrons que SiMany permet l'exploration d'un plus large champ d'architectures ainsi que l'étude des grandes lignes du comportement des logiciels sur celles-ci.

Nous développons une méthode de modélisation et de validation adaptée aux système parallèles structurés en couches hiérarchiques. Nous définissons deux notions : la concordance de modèle prouve que le modèle possède bien les propriétés dégagées par les spécifications; l'adéquation de service valide le protocole par rapport à son service. Nous appliquons notre méthode à la modélisation du protocole de télécommunication de niveau Transport (la couche 4 d'après la norme ISO sur l'interconnexion des systèmes ouverts). Nous étudions tout particulièrement la gestion de désynchronisations du Service de la couche Réseau, et le contrôle de flux avec réquisition de crédit du protocole de la couche Transport. Nous utilisons les réseaux de Petri à prédicats pour décrire le modèle du service rendu par le couche Réseau sous-jacente et nous en servir pour construire le modèle du protocole de ma couche Transport. nous prouvons que la notion d'abstraction peut s'étendre aux réseaux de Petri à prédicats. La preuve du déroulement correct du protocole est apportée en utilisant les invariants issus du modèle.

La dissémination d'informations (broadcast) est essentielle pour de nombreuses applications réparties. Celle-ci doit être efficace, c'est à dire limiter la redondance des messages, et assurer forte fiabilité et faible latence. Nous considérons ici les algorithmes répartis profitant des propriétés des topologies sous-jacentes. Cependant, ces propriétés et les paramètres dans les algorithmes sont hétérogènes. Ainsi, nous devons trouver une manière pour les comparer équitablement. D'abord, nous étudions les protocoles probabilistes de dissémination d'informations (gossip) exécutées sur trois graphes aléatoires. Les trois graphes représentent les topologies typiques des réseaux à grande-échelle : le graphe de Bernoulli, le graphe géométrique aléatoire et le graphe scale-free. Afin de comparer équitablement leurs performances, nous proposons un nouveau paramètre générique : le fanout effectif. Pour une topologie et un algorithme donnés, le fanout effectif caractérise la puissance moyenne de la dissémination des sites infectés. De plus, il simplifie la comparaison théorique des différents algorithmes sur une topologie. Après avoir compris l'impact des topologies et les algorithmes sur les performances , nous proposons un algorithme fiable et efficace pour la topologie scale-free.

Cette thèse concerne l'apprentissage de règles relationnelles à partir d'exemples et de contre-exemples, à l'aide d'algorithmes évolutionnaires. Nous étudions tout d'abord un biais de langage offrant une expressivité suffisamment riche pour permettre de couvrir à la fois le cadre de l'apprentissage relationnel par interprétations et les formalismes propositionnels classiques. Bien que le coût de l'induction soit caractérisé par la complexité NP-difficile du test de subsomption pour cette classe de langages, une solution capable de traiter en pratique les problèmes réels complexes est proposée. Le système SIAO1, qui utilise ce biais de langage pour l'apprentissage de règles relationnelles est ensuite présenté. Il est fondé sur une stratégie de recherche évolutionnaire qui se distingue principalement des approches classiques par: - des opérateurs de mutation et de croisement dirigés par la théorie du domaine et par les exemples d'apprentissage; - le respect de la relation d'ordre définie sur le langage. L'évaluation du système sur plusieurs bases faisant référence en apprentissage automatique montre que SIAO1 est polyvalent, se compare favorablement aux autres approches et sollicite peu l'utilisateur en ce qui concerne la spécification de biais de recherche ou d'évaluation. La troisième partie de ce travail propose deux architectures parallèles génériques derivées des modèles maître-esclave asynchrone et du pipeline. Elles sont étudiées dans le cadre de l'extraction de connaissances à partir de données à l'aide de SIAO1 du point de vue de l'accélération qu'elles procurent d'une part et de leur capacité à changer d'échelle d'autre part. Un modèle de prédiction simple mais précis des performances de chacune des architectures parallèles est également proposé.

Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique. / Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs.