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.

Beaucoup de services vitaux de la vie quotidienne dépendent de systèmes d'ingénierie hautement complexes et interconnectés; Ces systèmes sont constitués d'un grand nombre de capteurs interconnectés, d'actionneurs et de composants du système. L'étude des systèmes interconnectés joue un rôle important dans l'étude de la fiabilité des systèmes dynamiques; car elle permet d'étudier les propriétés d'un système interconnecté en analysant ses sous-composants moins complexes. Le diagnostic des pannes est essentiel pour assurer des opérations sûres et fiables des systèmes de contrôle interconnectés. Dans toutes les situations, le système global et / ou chaque sous-système peuvent être analysés à différents niveaux pour déterminer la fiabilité du système global. Dans certains cas, il est important de déterminer les informations anormales des variables internes du sous-système local, car ce sont les causes qui contribuent au fonctionnement anormal du processus global. Cette thèse porte sur les défis de l'application de la théorie inverse du système et des techniques FDD basées sur des modèles pour traiter le problème articulaire du diagnostic des fautes et de l'analyse des causes racines (FD et RCA). Nous étudions ensuite le problème de l'inversibilité de la gauche, de l'observabilité et de la diagnosticabilité des fauts du système interconnecté, formant un algorithme FD et RCA multi-niveaux basé sur un modèle. Ce système de diagnostic permet aux composants individuels de surveiller la dynamique interne localement afin d'améliorer l'efficacité du système et de diagnostiquer des ressources de fautes potentielles pour localiser un dysfonctionnement lorsque les performances du système global se dégradent. Par conséquent, un moyen d'une combinaison d'intelligence locale avec une capacité de diagnostic plus avancée pour effectuer des fonctions FDD à différents niveaux du système est fourni. En conséquence, on peut s'attendre à une amélioration de la localisation des fauts et à de meilleurs moyens de maintenance prédictive. La nouvelle structure du système, ainsi que l'algorithme de diagnostic des fautes, met l'accent sur l'importance de la RCA de défaut des dispositifs de terrain, ainsi que sur l'influence de la dynamique interne locale sur la dynamique globale. Les contributions de cette thèse sont les suivantes: Tout d'abord, nous proposons une structure de système non linéaire interconnecté inversible qui garantit le fauts dans le sous-système de périphérique de terrain affecte la sortie mesurée du système global de manière unique et distincte. Une condition nécessaire et suffisante est développée pour assurer l'inversibilité du système interconnecté qui nécessite l'inversibilité de sous-systèmes individuels. Deuxièmement, un observateur interconnecté à deux niveaux est développé; Il se compose de deux estimateurs d'état, vise à fournir des estimations précises des états de chaque sous-système, ainsi que l'interconnexion inconnue. En outre, il fournira également une condition initiale pour le reconstructeur de données et le filtre de fauts local une fois que la procédure FD et RCA est déclenchée par tout fauts. D'une part, la mesure utilisée dans l'estimateur de l'ancien sous-système est supposée non accessible; La solution est de la remplacer par l'estimation fournie par l'estimateur de ce dernier sous-système. / Many of the vital services of everyday life depend on highly complex and interconnected engineering systems; these systems consist of large number of interconnected sensors, actuators and system components. The study of interconnected systems plays a significant role in the study of reliability theory of dynamic systems, as it allows one to investigate the properties of an interconnected system by analyzing its less complicated subcomponents. Fault diagnosis is crucial in achieving safe and reliable operations of interconnected control systems. In all situations, the global system and/or each subsystem can be analyzed at different levels in investigating the reliability of the overall system; where different levels mean from system level down to the subcomponent level. In some cases, it is important to determine the abnormal information of the internal variables of local subsystem, in order to isolate the causes that contribute to the anomalous operation of the overall process. For example, if a certain fault appears in an actuator, the origin of that malfunction can have different causes: zero deviation, leakage, clogging etc. These origins can be represented as root cause of an actuator fault. This thesis concerns with the challenges of applying system inverse theory and model based FDD techniques to handle the joint problem of fault diagnosis & root cause analysis (FD & RCA) locally and performance monitoring globally. By considering actuator as individual dynamic subsystem connected with process dynamic subsystem in cascade, we propose an interconnected nonlinear system structure. We then investigate the problem of left invertibility, fault observability and fault diagnosability of the interconnected system, forming a novel model based multilevel FD & RCA algorithm. This diagnostic algorithm enables individual component to monitor internal dynamics locally to improve plant efficiency and diagnose potential fault resources to locate malfunction when operation performance of global system degrades. Hence, a means of acombination of local intelligence with a more advanceddiagnostic capability (combining fault monitoring anddiagnosis at both local and global levels) to performFDDfunctions on different levels of the plantis provided. As a result, improved fault localization and better predictive maintenance aids can be expected. The new system structure, together with the fault diagnosis algorithm, is the first to emphasize the importance of fault RCA of field devices, as well as the influences of local internal dynamics on the global dynamics. The developed model based multi-level FD & RCA algorithm is then a first effort to combine the strength of the system level model based fault diagnosis with the component level model based fault diagnosis. The contributions of this thesis include the following: Firstly, we propose a left invertible interconnected nonlinear system structure which guarantees that fault occurred in field device subsystem will affect the measured output of the global system uniquely and distinguishably. A necessary and sufficient condition is developed to ensure invertibility of the interconnected system which requires invertibility of individual subsystems. Second, a two level interconnected observer is developed which consists of two state estimators, aims at providing accurately estimates of states of each subsystem, as well as the unknown interconnection. In addition, it will also provide initial condition for the input reconstructor and local fault filter once FD & RCA procedure is triggered by any fault. Two underlyingissues are worth to be highlighted: for one hand, the measurement used in the estimator of the former subsystem is assumed not accessible; the solution is to replace it by the estimate provided by the estimator of the latter subsystem. In fact, this unknown output is the unknown interconnection of the interconnected system, and also the input of the latter subsystem.