Academic literature on the topic 'Tolérance aux pannes byzantines'

International audience This paper focuses on fault tolerance of super-nodes in P2P-SIP systems. These systems are characterized by high volatility of super-nodes. Most fault-tolerant proposed solutions are only for physical defects. They do not take into consideration the timing faults that are very important for multimedia applications such as telephony. This paper proposes a timing and physical fault tolerant mechanism based on P2P overlay with two levels for P2P-SIP systems. The simulation results show that our proposition reduces mostly the nodes location latency and increases the probability to find the called nodes. Cet article met l'accent sur la tolérance aux pannes de super-noeuds dans les systèmes P2P-SIP. Ces systèmes sont caractérisés par une forte volatilité des super-noeuds. La plupart des solutions tolérant aux pannes proposées traitent des défaillances physiques et ne prennent pas en compte les défaillances temporelles qui sont aussi importantes pour des applications multimédia telle que la téléphonie. Cet article propose un mécanisme de tolérance aux pannes physiques et temporelles basé sur un réseau de recouvrement P2P à deux niveaux pour les systèmes P2P-SIP. Les résultats de simulation ont montré que notre proposition diminue considérablement la latence de localisation des noeuds ordinaires et augmente la probabilité de les retrouver.

International audience Wireless sensor networks (WSN) face many implementation’s problems such as connectivity, security, energy saving, fault tolerance, interference, collision, routing problems, etc. In this paper, we consider a low-density WSN where the distribution of the sensors is poor, and the virtual architecture introduced by Wadaa and al which provides a powerful and fast partitioning of the network into a set of clusters. In order to effectively route the information collected by each sensor node to the base station (sink node, located at the center of the network), we propose a technique based on multiple communication frequencies in order to avoid interferences during the communications. Secondly, we propose an empty clusters detection algorithm, allowing to know the area actually covered by the sensors after the deployment, and therefore, giving the possibility to react accordingly. Finally, we also propose a strategy to allow mobile sensors (actuators) to move in order to: save the WSN’s connectivity, improve the routing of collected data, save the sensors’ energy, improve the coverage of the area of interest, etc. Les réseaux de capteurs sans fil (RCSF) font face à de nombreux problèmes dans leur mise en oeuvre, notamment aux problèmes de connectivité des noeuds, de sécurité, d'économie d'énergie, de tolérance aux pannes, d'interférence, de collision, de routage, etc. Dans ce document, nous considérons un RCSF peu dense, caractérisé par une mauvaise couverture de la zone d'inté-rêt, et l'architecture virtuel introduite par Wadaa et al qui permet de partitionner efficacement ce type de réseau en clusters. Dans l'optique de router optimalement les informations collectés par chaque capteur jusqu'à une station de base (noeud sink, supposé au centre du réseau), nous proposons une technique d'utilisation des fréquences multiples pour limiter les interférences lors des communications. Ensuite, nous proposons un algorithme de détection de clusters vides permettant d'avoir une vue globale de la répartition réelle des capteurs dans la zone d'intérêt, et ainsi donner la possibilité de réagir en conséquence. Nous proposons également une stratégie de déplacement des capteurs mobiles (actuators) afin de: sauvegarder la connectivité du RCSF, optimiser le routage, économiser l'énergie des capteurs, améliorer la couverture de la zone d'intérêt, etc.

Dans cette thèse, nous abordons trois défis majeurs dans la conception des systèmes de blockchain en particulier et des systèmes distribués tolérants aux pannes à grande échelle en général. Ce travail vise à améliorer directement la performance de tels systèmes, ainsi qu'à fournir des outils utiles pour le développement futur d'algorithmes distribués.Premièrement, nous explorons les limites de ce qui peut être réalisé avec une synchronisation minimale en concevant CryptoConcurrency—un système de transfert d'actifs qui, au lieu d'ordonner totalement toutes les requêtes des utilisateurs, traite les requêtes concurrentes en parallèle autant que possible. Contrairement à d'autres systèmes similaires, dans CryptoConcurrency, nous permettons aux utilisateurs d'avoir des comptes partagés et ne faisons pas l'hypothèse irréaliste qu'un compte d'utilisateur honnête n'est jamais accédé simultanément depuis deux dispositifs. CryptoConcurrency explore de nouveaux terrains théoriques en abordant les conflits de transactions de manière dynamique et non par paires, permettant aux propriétaires de chaque compte de choisir indépendamment leur mécanisme préféré de résolution de conflits.Ensuite, nous améliorons la performance du consensus—le problème de synchronisation au cœur de la plupart des systèmes distribués pratiques. Nous construisons le premier protocole de consensus qui parvient à combiner deux propriétés souhaitables : une terminaison extrêmement rapide dans des condi- tions favorables et une récupération élégante lorsque ces conditions ne sont pas remplies. La conception implique un nouveau type de preuves cryptographiques, avec une implémentation pratique et efficace.Enfin, nous nous attaquons au problème de la conception de protocoles distribués efficaces avec une participation pondérée. À cette fin, nous définissons plusieurs nouveaux problèmes d'optimisation, liés à la réduction ou, en d'autres termes, à la quantification des poids des participants d'une manière qui préserve d'importantes propriétés structurelles. Nous montrons comment les appliquer pour créer des variantes pondérées d'un large éventail de protocoles distribués avec très peu de surcharge par rapport à leurs homologues dans le modèle non pondéré plus simple. Pour ces problèmes d'optimisation, nous prouvons des bornes supérieures, fournissons un solveur pratique open-source approximatif qui satisfait ces bornes, et effectuons une étude empirique sur les distributions de poids provenant de systèmes de blockchain réels
In this dissertation, we address three major challenges in the design of blockchain systems in particular and large-scale fault-tolerant distributed systems in general. This work aims at improving the performance of such systems directly, as well as providing useful tools for future development of distributed algorithms.First, we explore the limits of what can be done with minimal synchronization by designing CryptoConcurrency—an asset transfer system that, instead of totally ordering all users' requests, processes concurrent requests in parallel as much as possible. Unlike other similar systems, in CryptoConcurrency, we allow the users to have shared accounts and do not make the unrealistic assumption that an honest user's account is never accessed from two devices concurrently. CryptoConcurrency explores novel theoretical grounds by addressing transaction conflicts in a dynamic, non-pairwise manner, allowing the owners of each account to independently choose their preferred mechanism for conflict resolution. Then, we improve the performance of consensus—the synchronization problem at the heart of most practical distributed systems. We build the first consensus protocol that manages to combine two desirable properties: extremely fast termination in favorable conditions and graceful recovery when such conditions are not met. The design involves a novel type of cryptographic proofs, with an efficient practical implementation.Finally, we set out to tackle the problem of designing efficient distributed protocols with weighted participation. To this end, we define several new optimization problems, related to reducing or, in other words, quantizing the weights of the participants in a way that preserves important structural properties. We show how to apply them to make weighted-model variants of a large class of distributed protocols with very little overhead compared to their counterparts in the simpler non-weighted model. For these optimization problems, we prove upper bounds, provide a practical open-source approximate solver that satisfies these upper bounds, and perform an empirical study on the weight distributions from real-world blockchain systems

Une communication fiable est une primitive fondamentale dans les systèmes distribués sujets aux pannes Byzantines (c'est-à-dire arbitraires et éventuellement malveillants) pour garantir l'intégrité, l’authenticité et la livraison des messages échangés entre les processus. Son adoption pratique dépend fortement des hypothèses du système. Plusieurs solutions ont été proposées jusqu'à présent dans la littérature mettant en œuvre une telle primitive, mais certaines manquent d'évolutivité et / ou exigent des conditions de réseau topologiques difficiles à vérifier. Cette thèse vise à étudier et à résoudre certains des problèmes et défis ouverts implémentant une telle primitive de communication. Plus précisément, nous analysons comment une primitive de communication fiable peut être implémentée dans 1) un système distribué statique où un sous-ensemble de processus est compromis, 2) un système distribué dynamique où une partie des processus est Byzantiné, et 3) un système distribué statique où chaque processus peut être compromis et récupérer. Nous définissons plusieurs protocoles plus efficaces et nous caractérisons des conditions de réseau alternatives garantissant leur exactitude
Reliable communication is a fundamental primitive in distributed systems prone to Byzantine (i.e. arbitrary, and possibly malicious) failures to guarantee the integrity, delivery, and authorship of the messages exchanged between processes. Its practical adoption strongly depends on the system assumptions. Several solutions have been proposed so far in the literature implementing such a primitive, but some lack in scalability and/or demand topological network conditions computationally hard to be verified. This thesis aims to investigate and address some of the open problems and challenges implementing such a communication primitive. Specifically, we analyze how a reliable communication primitive can be implemented in 1) a static distributed system where a subset of processes is compromised, 2) a dynamic distributed system where part of the processes is Byzantine faulty, and 3) a static distributed system where every process can be compromised and recover. We define several more efficient protocols and we characterize alternative network conditions guaranteeing their correctness

La recherche sur les cadres applicatifs de la blockchain propose rarement une évaluation de performances. Cette thèse propose une méthodologie complète pour aider les intégrateurs logiciels à mieux comprendre et mesurer l'influence des paramètres de configuration sur la qualité globale des performances du service à long terme. Afin d'améliorer les performances, le nouveau protocole de consensus adaptatif Sabine (Self-Adaptive BlockchaIn coNsEnsus) est proposé afin de modifier dynamiquement l'un de ces paramètres dans le cadre du consensus PBFT. Le paramètre de configuration de ce consensus est le nombre de validateurs impliqués et résulte d'un compromis entre sécurité et performance. Le protocole Sabine vient donc maximiser ce nombre sous réserve que le débit de sortie corresponde au débit d'entrée. Sabine est évaluée et validée dans des contextes réels, dont les résultats montrent que Sabine a une erreur relative acceptable entre les débits de transaction demandée et engagée. Deux nouveaux algorithmes de sélection des validateurs sont proposés et renversent le paradigme aléatoire des protocoles actuels pour choisir les nœuds amenant à de meilleures performances. Le premier se base sur un système de réputation récompensant les nœuds les plus rapides. Le second sélectionne les nœuds les plus proches en imposant un roulement continu de la sélection. Ces deux algorithmes ont été simulés et leurs impacts sur la décentralisation discutés. Cette sélection, associée avec Sabine, permet d'améliorer la sécurité en laissant plus de marge au système pour augmenter le nombre de validateurs. Ces différents travaux ouvrent la voie à des chaînes plus réactives, avec moins de latence et plus de débit
Research on blockchain application frameworks rarely offers performance evaluation. This thesis proposes a comprehensive methodology to help software integrators better understand and measure the influence of configuration parameters on the overall quality of long-term service performance. In order to improve performance, the new adaptive consensus protocol Sabine (Self-Adaptive BlockchaIn coNsEnsus) is proposed to dynamically modify one of these parameters in the PBFT consensus. The configuration parameter of this consensus is the number of validators involved and result of a trade-off between security and performance. The Sabine protocol maximises this number provided that the output rate matches the input rate. Sabine is evaluated and validated in real-world settings, the results of which show that Sabine has an acceptable relative error between the requested and committed transaction rates. Two new validator selection algorithms are proposed that reverse the random paradigm of current protocols to select the nodes leading to better performance. The first is based on a reputation system that rewards the fastest nodes. The second selects the closest nodes by imposing a continuous rotation of the selection. These two algorithms have been simulated and their impact on decentralisation discussed. This selection, associated with Sabine, improves security by giving the system more margin to increase the number of validators. This work opens the way to more reactive chains, with less latency and more throughput

La Tolérance aux pannes Byzantines (BFT) est de plus en plus crucial avec l'évolution d'applications et en raison de la croissance de l'innovation technologique en informatique. Bien que des dizaines de protocoles BFT aient été introduites dans les années précédentes, leur mise en œuvre ne semble pas satisfaisant. Pour faire face à cette complexité, due à la dependence d'un protocol d'une situation, nous tentons une approche qui permettra de sélectionner un protocole en fonction d'une situation. Ceci nous paraît, en s'inspirant de tout système d'encrage, comme une démarche nécessaire pour aborder la problématique de la BFT. Dans cette thèse, nous introduisons un modèle de sélection ainsi que l'algorithme qui permet de simplifier et d'automatiser le processus d'élection d'un protocole. Ce mécanisme est conçu pour fonctionner selon 3 modes : statique, dynamique et heuristique. Les deux derniers modes, nécessitent l'introduction d'un système réactif, nous ont conduits à présenter un nouveau modèle BFT : Adapt. Il réagit à tout changement et effectue, d'une manière adaptée, la commutation entre les protocoles d'une façon dynamique. Le mode statique permet aux utilisateurs de BFT de choisir un protocole BFT en une seule fois. Ceci est très utile dans les services Web et les " Clouds " où le BFT peut être fournit comme un service inclut dans le contrat (SLA). Ce mode est essentiellement conçu pour les systèmes qui n'ont pas trop d'états fluctuants. Pour ce faire, un processus d'évaluation est en charge de faire correspondre, à priori, les préférences de l'utilisateur aux profils du protocole BFT nommé, en fonction des critères de fiabilité et de performance. Le protocole choisi est celui qui réalise le meilleur score d'évaluation. Le mécanisme est bien automatisé à travers des matrices mathématiques, et produit des sélections qui sont raisonnables. D'autres systèmes peuvent cependant avoir des conditions flottantes, il s'agit de la variation des charges ou de la taille de message qui n'est pas fixe. Dans ce cas, le mode statique ne peut continuer à être efficace et risque de ne pas pouvoir s'adapter aux nouvelles conditions. D'où la nécessité de trouver un moyen permettant de répondre aux nouvelles exigences d'une façon dynamique. Adapt combine un ensemble de protocoles BFT ainsi que leurs mécanismes de commutation pour assurer l'adaptation à l'évolution de l'état du système. Par conséquent, le "Meilleur" protocole est toujours sélectionné selon l'état du système. On obtient ainsi une qualité optimisée de service, i. E. , la fiabilité et la performance. Adapt contrôle l'état du système grâce à ses mécanismes d'événements, et utilise une méthode de "Support Vecor Regrssion" pour conduire aux prédictions en temps réel pour l'exécution des protocoles (par exemple, débit, latence, etc. ). Ceci nous conduit aussi à un mode heuristique. En utilisant des heuristiques prédéfinies, on optimise les préférences de l'utilisateur afin d'améliorer le processus de sélection. L'évaluation de notre approche montre que le choix du "meilleur" protocole est automatisé et proche de la réalité de la même façon que dans le mode statique. En mode dynamique, Adapt permet toujours d'obtenir la performance optimale des protocoles disponibles. L'évaluation démontre, en plus, que la performance globale du système peut être améliorée de manière significative. Explorer d'autres cas qui ne conduisent pas de basculer entre les protocoles. Ceci est rendu possible grâce à la réalisation des prévisions d'une grande precision qui peuvent atteindre plus de 98% dans de nombreux cas. La thèse montre que cette adaptabilité est rendue possible grâce à l'utilisation des heuristiques dans un mode dynamique
Byzantine Fault Tolerance (BFT) is becoming crucial with the revolution of online applications and due to the increasing number of innovations in computer technologies. Although dozens of BFT protocols have been introduced in the previous decade, their adoption by practitioners sounds disappointing. To some extant, this indicates that existing protocols are, perhaps, not yet too convincing or satisfactory. The problem is that researchers are still trying to establish 'the best protocol' using traditional methods, e. G. , through designing new protocols. However, theoretical and experimental analyses demonstrate that it is hard to achieve one-size-fits-all BFT protocols. Indeed, we believe that looking for smarter tac-tics like 'fasten fragile sticks with a rope to achieve a solid stick' is necessary to circumvent the issue. In this thesis, we introduce the first BFT selection model and algorithm that automate and simplify the election process of the 'preferred' BFT protocol among a set of candidate ones. The selection mechanism operates in three modes: Static, Dynamic, and Heuristic. For the two latter modes, we present a novel BFT system, called Adapt, that reacts to any potential changes in the system conditions and switches dynamically between existing BFT protocols, i. E. , seeking adaptation. The Static mode allows BFT users to choose a single BFT protocol only once. This is quite useful in Web Services and Clouds where BFT can be sold as a service (and signed in the SLA contract). This mode is basically designed for systems that do not have too fuctuating states. In this mode, an evaluation process is in charge of matching the user preferences against the profiles of the nominated BFT protocols considering both: reliability, and performance. The elected protocol is the one that achieves the highest evaluation score. The mechanism is well automated via mathematical matrices, and produces selections that are reasonable and close to reality. Some systems, however, may experience fluttering conditions, like variable contention or message payloads. In this case, the static mode will not be e?cient since a chosen protocol might not fit the new conditions. The Dynamic mode solves this issue. Adapt combines a collection of BFT protocols and switches between them, thus, adapting to the changes of the underlying system state. Consequently, the 'preferred' protocol is always polled for each system state. This yields an optimal quality of service, i. E. , reliability and performance. Adapt monitors the system state through its Event System, and uses a Support Vector Regression method to conduct run time predictions for the performance of the protocols (e. G. , throughput, latency, etc). Adapt also operates in a Heuristic mode. Using predefined heuristics, this mode optimizes user preferences to improve the selection process. The evaluation of our approach shows that selecting the 'preferred' protocol is automated and close to reality in the static mode. In the Dynamic mode, Adapt always achieves the optimal performance among available protocols. The evaluation demonstrates that the overall system performance can be improved significantly too. Other cases explore that it is not always worthy to switch between protocols. This is made possible through conducting predictions with high accuracy, that can reach more than 98% in many cases. Finally, the thesis shows that Adapt can be smarter through using heursitics

Au cours de la dernière décennie, l'informatique en nuage (Cloud Computing) suscita un important changement de paradigme dans de nombreux systèmes d'information. Ce nouveau paradigme s'illustre principalement par la délocalisation de l'infrastructure informatique hors du parc des entreprises, permettant ainsi une utilisation des ressources à la demande. La prise en charge de serveurs locaux s'est donc vue peu à peu remplacée par la location de serveurs distants, auprès de fournisseurs spécialisés tels que Google, Amazon, Microsoft. Afin d'assurer la pérennité d'un tel modèle économique, il apparaît nécessaire de fournir aux utilisateurs diverses garanties relatives à la sécurité, la disponibilité, ou encore la fiabilité des ressources mises à disposition. Ces facteurs de qualité de service (QoS pour Quality of Service) permettent aux fournisseurs et aux utilisateurs de s'accorder sur le niveau de prestation escompté. En pratique, les serveurs mis à disposition des utilisateurs doivent épisodiquement faire face à des fautes arbitraires (ou byzantines). Il s'agit par exemple de ruptures temporaires du réseau, du traitement de messages corrompus, ou encore d’arrêts inopinés. Le contexte d'informatique en nuage s'est vu néanmoins propice à l'émergence de technologies telles que la virtualisation ou la réplication de machines à états. De telles technologies permettent de pallier efficacement à l’occurrence de pannes via l'implémentation de protocoles de tolérance aux pannes.La tolérance aux fautes byzantines (BFT pour Byzantine Fault Tolerance) est un domaine de recherche implémentant les concepts de réplication de machines à états, qui vise à assurer la continuité et la fiabilité des services en présence de comportements arbitraires. Afin de répondre à cette problématique, de nombreux protocoles furent proposés. Ceux-ci se doivent d'être efficaces afin de masquer le surcoût lié à la réplication, mais également robustes afin de maintenir un niveau de performance élevé en présence de fautes. Nous constatons d'abord qu'il est délicat de relever ces deux défis à la fois: les protocoles actuels sont soit conçus pour être efficaces au détriment de leur robustesse, soit pour être robustes au détriment de leur efficacité. Cette thèse se focalise autour de cette problématique, l'objectif étant de fournir les instruments nécessaires à la conception de protocoles à la fois robustes et efficaces.Notre intérêt se porte principalement vers deux types de dénis de service liés à la gestion des requêtes. Le premier de ces dénis de service est causé par la corruption partielle d'une requête lors de son émission par un client. Le deuxième est causé par l'abandon intentionnel d'une requête lors de sa réception par un réplica. Afin de faire face efficacement à ces deux comportements byzantins, plusieurs mécanismes dédiés furent implémentés dans les protocoles de BFT robustes. En pratique, ces mécanismes engendrent d'importants surcoûts, ce qui nous permet d'introduire notre première contribution: la définition de plusieurs principes de conception génériques destinés à réduire ces surcoûts tout en assurant un niveau de robustesse équivalent.La seconde contribution de cette thèse illustre ER-PBFT, un nouveau protocole implémentant ces principes de conception sur PBFT, la référence en matière de tolérance aux fautes byzantines. Nous démontrons l'efficacité de notre nouvelle politique de robustesse, à la fois en présence de comportements byzantins mais également lors de scénarios sans faute.La troisième contribution illustre ER-COP, un nouveau protocole orienté à la fois vers l’efficacité et la robustesse, implémentant nos principes de conception sur COP, le protocole de BFT fournissant les meilleures performances à l'heure actuelle dans un environnement sans faute. Nous évaluons le surcoût engendré par l'intégration de notre politique de robustesse, et nous démontrons la capacité de ER-COP à tolérer l'occurrence de comportements byzantins
Over the last decade, Cloud computing instigated an important switch of paradigm in numerous information systems. This new paradigm is mainly illustrated by the re-location of the whole IT infrastructures out of companies’ warehouses. The use of local servers has thus being replaced by remote ones, rented from dedicated providers such as Google, Amazon, Microsoft.In order to ensure the sustainability of this economic model, it appears necessary to provide several guarantees to users, related to the security, availability, or even reliability of the proposed resources. Such quality of service (QoS) factors allow providers and users to reach an agreement on the expected level of dependability. Practically, the proposed servers must episodically cope with arbitrary faults (also called byzantine faults), such as incorrect/corrupted messages, servers crashes, or even network failures. Nevertheless, the Cloud computing environment encouraged the emergence of technologies such as virtualization or state machine replication. These technologies allow cloud providers to efficiently face the occurrences of faults through the implementation of fault tolerance protocols.Byzantine Fault Tolerance (BFT) is a research area involving state machine replication concepts, and aiming at ensuring continuity and reliability of hosted services in presence of any kind of arbitrary behaviors. In order to handle such threat, numerous protocols were proposed. These protocols must be efficient in order to counterbalance the extra cost of replication, and robust in order to lower the impact of byzantine behaviors on the system performance. We first noticed that tackling both these concerns at the same time is difficult: current protocols are either designed to be efficient at the expense of their robustness, or robust at the expense of their efficiency. We tackle this specific problem in this thesis, our goal being to provide the required tools to design both efficient and robust BFT protocols.Our focus is mainly dedicated to two types of denial-of-service attacks involving requests management. The first one is caused by the partial corruption of a request transmitted by a client. The second one is caused by the intentional drop of a request upon receipt. In order to face efficiently both these byzantine behaviors, several mechanisms were integrated in robust BFT protocols. In practice, these mecanisms involve high overheads, and thus lead to the significant performance drop of robust protocols compared to efficien ones. This assessment allows us to introduce our first contribution: the definition of several generic design principles, applicable to numerous existing BFT protocols, and aiming at reducing these overheads while maintaining the same level of robustness.The second contribution introduces ER-PBFT, a new protocol implementing these design principles on PBFT, the reference in terms of byzantine fault tolerance. We demonstrate the efficiency of our new robustness policy, both in fault-free scenarios and in presence of byzantine behaviors.The third contribution highlights ER-COP, a new BFT protocol dedicated to both efficiency and robustness, implementing our design principles on COP, the BFT protocol providing for now the best performances in a fault-free environment. We evaluate the additional cost introduced by our robustness policy, and we demonstrate ER-COP's ability to handle byzantine behaviors

Les systèmes d'information deviennent de plus en plus complexes et il est difficile de les garantir exempts de fautes. La réplication de machines à états est une technique permettant de tolérer les fautes, quelque soit leur nature, qu'elles soient logicielles ou matérielles. Cette thèse traite des protocoles de réplication de machines à états tolérant les fautes arbitraires, également appelées Byzantines. Ces protocoles doivent relever deux défis : (i) ils doivent être efficaces, c'est-à-dire que leurs performances doivent être les meilleurs possibles, afin de masquer le coût supplémentaire dû à la réplication et (ii) ils doivent être robustes, c'est-à-dire qu'une attaque ne doit pas faire baisser leurs performances de manière importante. Dans cette thèse nous observons qu'aucun protocole ne relève ces deux défis en même temps : les protocoles que nous connaissons aujourd'hui sont soit conçus pour être efficaces au détriment de leur robustesse, soit conçus pour être robustes au détriment de leurs performances. Une première contribution de cette thèse est la conception d'un nouveau protocole qui réunit le meilleur des deux mondes. Ce protocole, R-Aliph, combine un protocole efficace mais peu robuste avec un protocole robuste afin de fournir un protocole à la fois efficace et robuste. Nous évaluons ce protocole de manière expérimentale et montrons que ses performances en cas d'attaque sont égales aux performances du protocole robuste sous-jacent. De plus, ses performances dans le cas sans faute sont très proches des performances du protocole connu le plus efficace : la différence maximale de débit est inférieure à 6%. Dans la seconde partie de cette thèse nous observons que les protocoles conçus pour être robustes sont peu robustes en réalité. En effet, il est possible de concevoir une attaque dans laquelle leur perte de débit est supérieure à 78%. Nous identifions le problème de ces protocoles et nous concevons un nouveau protocole plus robuste que les précédents : RBFT. L'idée de base de ce protocole est d'exécuter en parallèle plusieurs instances d'un même protocole. Les performances de ces différentes instances sont surveillées de près afin de détecter tout comportement malicieux. Nous évaluons RBFT dans le cas sans faute et en cas d'attaque. Nous montrons que ses performances dans le cas sans faute sont comparables aux performances des protocoles considérés comme robustes. De plus, nous observons que la dégradation maximale de performance qu'un attaquant peut causer sur le système est inférieure à 3%, même dans le cas de la pire attaque possible
Information systems become more and more complex and it is difficult to guarantee that they are bug-free. State Machine Replication is a technique for tolerating faults, regardless their nature, whether they are software or hardware faults. This thesis studies Fault Tolerant State Machine Replication protocols that tolerate arbitrary, also called Byzantine, faults. These protocols face two challenges: (i) they must be efficient, i.e., their performance have to be the best ones, in order to mask the cost of the replication and (ii) they must be robust, i.e., an attack should not cause an important performance degradation. In this thesis, we observe that no protocol addresses both of these challenges: current protocols are either designed to be efficient but fail to be robust, or designed to be robust but exhibit poor performance. A first contribution of this thesis is the design of a new protocol which achieves the best of both worlds. This protocol, R-Aliph, combines an efficient but not robust protocol with a protocol designed to be robust. The result is a protocol that is both robust and efficient. We evaluate this protocol experimentally and show that its performance under attack equals the performance of the underlying robust protocol. Moreover, its performance in the fault-free case is close to the performance of the best known efficient protocol: the maximal throughput difference is less than 6%. In the second part of this thesis we analyze the state-of-the-art robust protocols and demonstrate that they are not effectively robust. Indeed, one can run an attack on each of these protocols such that the throughput loss is at least equal to 78%. We identify the problem of these protocols and design a new, effectively robust, protocol called RBFT. The main idea of this protocol is to execute several instances of a robust protocol in parallel and closely monitor their performance, in order to detect a malicious behaviour. We evaluate RBFT in the fault-free case and under attack. We observe that its performance in the fault-free case is equivalent to the performance of the other so-called robust BFT protocols. Moreover, we show that the maximal throughput degradation, under the worst possible attack, is less than 3%

La tolérance aux pannes est une propriété indispensable des réseaux optiques à cause de la bande passante importante offerte par la technologie WDM (Wavelength Division Multiplexing). La tolérance aux pannes signifie que le réseau a la capacité de maintenir un service acceptable, même si une panne dans le réseau survient. Dans cette thèse, nous étudions la tolérance aux pannes des réseaux optiques. Le travail effectué dans cette thèse s'articule autour de deux grandes parties. La première partie aborde la tolérance aux pannes des réseaux optiques formés d'un domaine unique. Dans cette partie, nous analysons et classons, dans un premier temps, les différents mécanismes proposés dans la littérature pour la protection de ce type de réseau. Dans un deuxième temps, notre étude se focalise sur la protection par p-cycles à cause des avantages offerts par ce mécanisme de protection : faible temps de reprise et bonne utilisation de ressources. La difficulté majeure de ce mécanisme réside dans le calcul de l'ensemble le plus efficace possible de p-cycles protégeant le réseau pour une certaine charge. Pour cela nous proposons une solution pour calculer un ensemble de p-cycles efficace protégeant le réseau, et améliorant les performances des solutions proposées dans la littérature. La première partie de cette thèse est réservée à la tolérance aux pannes d'un domaine simple car elle fait l'hypothèse que chaque noeud dans le réseau possède une vision entière et détaillée de la topologie physique du réseau. Une telle hypothèse n'est plus valide quand il s'agit d'un réseau de taille importante, un réseau multi-domaine par exemple. Très peu d'études scientifiques ont été menées sur la tolérance aux pannes des réseaux multi-domaines. La deuxième partie de cette thèse décrit les travaux actuels portant sur la protection contre les pannes dans les réseaux multi-domaines et propose une comparaison quantitative et qualitative entre les solutions proposées dans la littérature. Nous proposons également une solution qui se base sur la protection par p-cycles et l'agrégation de topologie. Elle surmonte les problèmes des solutions proposées dans la littérature
Survivability in optical network is an important issue due to the huge bandwidth offered by optical technology. Survivability means that the network has the ability to maintain an acceptable service level even after an occurrence of failures within the network. In this thesis, we study the survivability in optical networks. Indeed, our work focuses on two main parts. The first part addresses the survivability in networks composed of one single domain. Firstly, we study and classify the various mechanisms of survivability proposed in the literature. Then we focus on p-cycles design. The major challenge of p-cycle design resides in finding an optimal set of p-cycles protecting the network for a given working capacity. In our thesis we propose a novel heuristic approach, which computes an efficient set of p-cycles protecting the network in one step. Our heuristic approach takes into consideration two main criteria: the redundancy and the number of p-cycles involved in the solution. The mechanisms studied in the first part are typically destined to single-domain protection, because they assume that each node in the network may have a complete vision of the physical topology of the network. Such an assumption is not realistic in the case of large networks, such as a multi-domain networks. Few works have focused on survivability in multi-domain optical networks. The second part of this thesis describes and evaluates existing solutions and compares their performances. We propose also a solution based on p-cycles and topology aggregation which overcomes the different problems of the existing solutions

L'objectif premier de cette thèse est de proposer un protocole de tolérance aux pannes par recouvrement arrière pour le modèle à objets actifs asynchrones communicants ASP (Asynchronous Sequential Processes) et son implémentation en Java ProActive. Cette thèse généralise la problématique soulevée par le développement de ce protocole : nous étudions le recouvrement d'une application répartie depuis un état global non cohérent. Nous proposons donc dans un premier temps un protocole par points de reprise et son implémentation ne supposant pas que les états globaux soient cohérents. Nous montrons à travers des expérimentations réalistes utilisant des applications réparties communicantes que notre solution et son implémentation présentent de bonnes performances. Nous contribuons aussi de manière plus générale à l'étude du recouvrement depuis un état global non cohérent en définissant formellement une nouvelle condition de recouvrabilité, la P-cohérence, basée sur la notion de promesse d'évènement. Cette définition s'intègre dans un formalisme événementiel capable de prendre en compte la sémantique de n'importe quel système ; elle est donc applicable dans un cadre général. En particulier, en appliquant ce formalisme au modèle ASP, nous prouvons la correction de notre protocole en montrant que les états globaux formés durant l'exécution sont toujours recouvrables. Enfin, nous contribuons plus spécifiquement au domaine des grilles de calcul en proposant une extension de notre protocole et son implémentation adaptée à ce contexte. Cette extension se base sur la constitution automatique de groupes de recouvrement au déploiement de l'application. Elle permet une répartition indépendante des mémoires stables et un confinement des effets d'une panne au seul groupe concerné.

Les grilles et les grappes sont des architectures de plus en plus utilisées dans le domaine du calcul scientifique distribué. Le nombre important de constituants hétérogènes (processeurs, mémoire, interconnexion) dans ces architectures dynamiques font que le risque de défaillance est très important. Compte tenu de la durée considérable de l'exécution d'une application parallèle distribuée, ce risque de défaillance doit être contrôlé par l'utilisation de technique de tolérance aux pannes.
Dans ce travail, la représentation de l'état de l'exécution d'un programme parallèle est un graphe, dynamique, de flot de données construit à l'exécution. Cette description du parallélisme est indépendante du nombre de ressources et donc exploitée pour résoudre les problèmes liés à la dynamicité des plateformes considérées. La définition de formats portables pour la représentation des noeuds du graphe résout les problèmes d'hétérogénéité. La sauvegarde du graphe de flot de données d'une application durant son exécution sur une plateforme, constitue des points de reprise pour cette application. Par la suite, une reprise est possible sur un autre type ou nombre de processus. Deux méthodes de sauvegarde / reprise, avec une analyse formelle de leurs complexités, sont présentées : SEL (Systematic Event Logging) et TIC (Theft-Induced Checkpointing). Des mesures expérimentales d'un prototype sur des applications caractéristiques montrent que le surcoût à l'exécution peut être amorti, permettant d'envisager des exécutions tolérantes aux pannes qui passent à l'échelle.

De nos jours, les circuits FPGAs à base de mémoire SRAM sont omniprésents dans les applications électroniques embarquées. Ainsi, ces circuits sont devenus un acteur principal dans l’amélioration du rendement de l’ensemble du spectre des systèmes-sur-puce (SoC). Néanmoins, les pannes se sont accentuées dans ces technologies émergentes, qu’il s’agisse de pannes permanentes provenant d’une forte densité d’intégration, associée à une complexité élevée des procédés de fabrication, ou de pannes transitoires découlant des particules chargées qui heurtent les FPGAs dans leurs environnements d’exploitation. La tolérance aux pannes des circuits FPGAs à base de mémoire SRAM est donc un paramètre essentiel pour assurer la sûreté de fonctionnement des applications implémentées. Dans le cadre de cette thèse, nous proposons une stratégie de tolérance aux pannes qui s’accommode des contraintes de fiabilité pour un système implémenté dans un FPGA à base de mémoire SRAM. Cette stratégie présente une grande flexibilité et un coût faible comparé à la technique de la redondance modulaire triple (TMR), et permet la gestion en temps d’exécution qui est une caractéristique importante pour les applications critiques. Dans cette thèse, nous proposons également des tests spécifiques, appelés algorithmes March, qui permettent de détecter les pannes intra-mots dans la mémoire de configuration d’un circuit FPGA- SRAM. Ces tests présentent l’avantage de bénéficier d’une implémentation rapide et d’obtenir un taux de couverture élevé
Nowadays, SRAM-based FPGAs are omnipresent for embedded electronic applications. Consequently, these circuits became the key player of the overall System-On-Chip (SoC) yield enhancement. However, faults are increasingly pronounced in these emergent technologies, from permanent faults arising from circuit processing at nanometer scales to transient soft errors arising from high-energy particle hits. So fault-tolerance of SRAM-based FPGA is an important system metric to ensure the dependability of embedded applications. The first part of this thesis exposes a comprehensive technique to cope with multiple faults in applications implemented in SRAM-based FPGA without incurring substantial area, power, or performance penalties. This approach has three main benefits compared to redundancy-based fault-tolerance: it’s very low overhead, the option for runtime management, and its complete flexibility. Run-time management can be a very valuable feature of a system, particularly for mission-critical applications. This fault-tolerance approach handles runtime problems on-line, minimizing the amount of system downtime and eliminating the need for outside intervention. The last part of this thesis is oriented toward configuration memory array of SRAM-based FPGA test and diagnostic. New fault models in configuration frames and March algorithms are proposed. These tests have the advantage to benefit from a fast implementation and achieving high fault coverage