Detectores de falhas não confiáveis tradicionais são oráculos disponíveis localmente para processos deumsistema distribuído que fornecem uma lista de processos suspeitos de terem falhado. Este trabalho propõe um novo e flexível detector de falhas não confiável, chamado Impact FD, que fornece como saída um valor trust level que é o grau de confiança no sistema. Ao expressar a relevância de cada processo por um valor de fator de impacto, bem como por uma margem de falhas aceitáveis do sistema, o Impact FD permite ao usuário ajustar a configuração do detector de falhas de acordo com os requisitos da aplicação: em certos cenários, o defeito de umprocesso de baixo impacto ou redundante não compromete a confiança no sistema, enquanto o defeito de um processo de alto fator de impacto pode afetá-la seriamente. Assim, pode ser adotada uma estragégia de monitoramento com maior ou menor rigor. Em particular, definimos algumas propriedades de flexibilidade que caracterizam a capacidade do Impact FD para tolerar uma certa margem de falhas ou falsas suspeitas, ou seja, a sua capacidade de fornecer diferentes conjuntos de respostas que levam o sistema a estados confiáveis. O Impact FD é adequado para sistemas que apresentam redundância de nodos, heterogeneidade de nodos, recurso de agrupamento e permite uma margem de falhas que não degrada a confiança no sistema. Nós também mostramos que algumas classes do Impact FD são equivalentes a § e ­, que são detectores de falhas fundamentais para contornar a impossibilidade de resolver o problema do consenso em sistemas de transmissão de mensagens assíncronas na presença de falhas. Adicionalmente, com base em pressupostos de sincronia e nas abordagens baseada em tempo e padrão de mensagem, apresentamos três algoritmos que implementam o Impact FD. Os resultados da avaliação de desempenho usando traces reais do PlanetLab confirmam o grau de aplicabilidade flexível do nosso detector de falhas e, devido à margem aceitável de falhas, o número de falsas respostas ou suspeitas pode ser tolerado quando comparado a tradicionais detectores de falhas não confiáveis. / Traditional unreliable failure detectors are per process oracles that provide a list of processes suspected of having failed. This work proposes a new and flexible unreliable failure detector (FD), denoted the Impact FD, that outputs a trust level value which is the degree of confidence in the system. By expressing the relevance of each process by an impact factor value as well as a margin of acceptable failures of the system, the Impact FD enables the user to tune the failure detection configuration in accordance with the requirements of the application: in some scenarios, the failure of low impact or redundant processes does not jeopardize the confidence in the system, while the crash of a high impact process may seriously affect it. Either a softer or stricter monitoring strategy can be adopted. In particular, we define some flexibility properties that characterize the capacity of the Impact FD to tolerate a certain margin of failures or false suspicions, i.e., its capacity of providing different sets of responses that lead the system to trusted states. The Impact FD is suitable for systems that present node redundancy, heterogeneity of nodes, clustering feature, and allow a margin of failures which does not degrade the confidence in the system. We also show that some classes of the Impact FD are equivalent to ­ and § which are fundamental FDs to circumvent the impossibility of solving the consensus problem in asynchronous message-passing systems in presence of failures. Additionally, based on different synchrony assumptions and message-pattern or timer-based approaches, we present three algorithms which implement the Impact FD. Performance evaluation results using real PlanetLab traces confirmthe degree of flexible applicability of our failure detector and, due to the accepted margin of failures, that false responses or suspicions may be tolerated when compared to traditional unreliable failure detectors.

Os circuitos integrados recentes baseados em tecnologias nanoeletrônicas estão significativamente mais vulneráveis a falhas transientes. Os erros gerados são assim também mais críticos do que eram antes. Esta tese apresenta uma nova virtude em termos de confiabilidade dos circuitos assíncronos quase-insensíveis aos atrasos (QDI): a sua grande habilidade natural para mitigar falhas transientes de longa duração, que são severas em circuitos síncronos modernos. Uma metodologia para avaliar comparativamente os efeitos de falhas transientes tanto em circuitos síncronos como em circuitos assíncronos QDI é apresentada. Além disso, um método para obter a habilidade de mitigação de falhas transientes dos elementos de memória de circuitos QDI (ou seja, os C-elements) é também proposto. Por fim, técnicas de mitigação são sugeridas para aumentar ainda mais a atenuação de falhas transientes por parte dos Celements e, por consequência, também a robustez dos sistemas assíncronos QDI. / Recent deep-submicron technology-based ICs are significantly more vulnerable to transient faults. The arisen errors are thus also more critical than they have ever been before. This thesis presents a further novel benefit of the Quasi-Delay Insensitive (QDI) asynchronous circuits in terms of reliability: their strong natural ability to mitigate longduration transient faults that are severe in modern synchronous circuits. A methodology to evaluate comparatively the transient-fault effects on synchronous and QDI asynchronous circuits is presented. Furthermore, a method to obtain the transient-fault mitigation ability of the QDI circuits’ memory elements (i.e., the C-elements) is also proposed. Finally, mitigation techniques are suggested to increase even more the Celements’ transient-fault attenuation, and thus also the QDI asynchronous systems’ robustness.

Esta dissertação aborda um ramo da computação que se encontra em crescente desenvolvimento: a computação em tempo real. Os sistemas de computação tempo real surgiram a partir da necessidade de substituição do controle humano, que muitas vezes é falho, em situações complexas ou críticas, onde máxima confiabilidade e disponibilidade são exigidas para garantir a segurança do sistema. A área de aplicação diferencia-se de outras convencionais por possuir diferentes tipos de restrições de tempo e operar em ambientes não-determinísticos. Entretanto, atualmente tais sistemas estão tornando-se grandes, complexos, distribuídos, adaptativos e cada vez mais presentes nas aplicações do dia-a-dia,o que tende a exigir soluções mais simples e generalizadas. Pelo fato de tais sistemas normalmente atuarem sobre aplicações críticas, importante salientar que, em algumas situações, pequenos erros no sistema podem levar a grandes catástrofes. Mesmo atrasos mínimos no tempo de resposta são problemáticos, podendo ocasionar degradações ou ações erradas no mundo físico controlado pelo sistema tempo real. Como nestes casos máxima confiabilidade e disponibilidade são exigidas para garantir a sua segurança, tornou-se importante a construção de sistemas tempo real tolerantes a falhas. Dessa forma, é visivelmente crescente a necessidade de utilização de mecanismos capazes de abordar os requisitos de tempo real e tolerância a falhas de forma integrada durante o desenvolvimento do sistema. Assim, o processo de desenvolvimento de sistemas tempo real confiáveis torna-se mais simples e mais eficiente. A necessidade de maior conhecimento do uso de tolerância a falhas para obter segurança no funcionamento de aplicações tempo real levou ao desenvolvimento deste trabalho, onde buscou-se um caminho de solução para a adequação das técnicas de tolerância a falhas a estas aplicações. Sabe-se que para produzir software confiável e, desta forma de maior qualidade, além do emprego de boas técnicas de engenharia de software, é necessário compreender os principais conceitos e técnicas de tolerância a falhas. Por outro lado, é importante ter-se conhecimento dos mecanismos oferecidos pelas diversas camadas de software de um sistema - protocolo de comunicação, sistema operacional e linguagem de programação - para apoiar estas atividades de tolerância a falhas. Este trabalho busca analisar os mecanismos e técnicas usados na implementação de software tolerante a falhas frente às situações mencionadas, uma vez que nem todas as técnicas conhecidas podem ser indistintamente aplicáveis a estas situações. Os resultados desta análise são organizados na forma de uma taxonomia, visando assim auxiliar projetistas de desenvolvimento de software a tomarem decisões importantes na construção de sistemas tempo real tolerantes a falhas. Os mecanismos são agrupados de acordo com o nível de implementação: sistemas operacionais, linguagens de programação e protocolos de comunicação, destacando suas características e aplicabilidade. Por fim uso da classificação é demonstrado com a análise de três casos-exemplo. / This dissertation is about a, computer science field which is in growing development, that is, real-time computation. Real-time computing systems have emerged from the necessity of substituting. human control which is sometimes failed in complex or critical situations. In these ones maximum availability and reliability are requested in order to guarantee the system dependability. The application area differs from the conventional ones because it has particular time constraints and operates in nondeterministic environments. Nevertheless, nowadays such systems are becoming large, complex, distributed and adaptive but tend to demand simpler and generalized solutions as they are more present in daily applications. Since such systems normally act on critical applications it is important to reinforce, that in some situations, subtle systems errors may generate big catastrophes. Even slight delays in response time are troublesome and they may cause degradation or wrong acts in physical world controlled by real-time systems. In these cases maximum reliability and availability are requested in order to guarantee system dependability. Thereby, the requirement of including mechanisms capable of achieving real-time and fault tolerance in an integrated way during the system design has been increased. Thus, the developing process of reliable real-time systems becomes simpler and more effective. The necessity of improving designers knowledge on using fault tolerance in order to obtain dependability on real-time applications has motivated this study. Our main goal has been to find an adequate way of using fault tolerance techniques to these applications. It is known that the development of reliable software not only requires appropriate software engineering techniques but also demands understanding of main politics and mechanisms used to implement fault tolerance techniques in these situations. Otherwise, it is very important to know the related support that is offered by the different software levels of a system - communication protocol, operating system and programming language. This study has as purpose analyzing the mechanisms and techniques used in implementation of fault-tolerant software applied to the previously mentioned situations. The basic supposition is that not all the known techniques may be applied indistinctly to these situations. The properties of the software are organized according to a taxonomy, where the mechanisms are bracketed in groups according to implementation level: operating systems, programming languages and communication protocols. In this presentation, the characteristics and applicability of the software tools are stood out in order to help developing-software designers to decide what is important to build faulttolerant software. Finally, the use of the classification is demonstrated by analyzing three case-examples.

A utilização de técnicas de tolerância a falhas em software é uma forma de baixo custo para proteger processadores contra soft errors. Contudo, elas causam aumento no tempo de execução e utilização de memória. Em consequência disso, o consumo de energia também aumenta. Sistemas que operam com restrição de tempo ou energia podem ficar impossibilitados de utilizar tais técnicas. Por esse motivo, este trabalho propoe técnicas de tolerância a falhas em software com custos no desempenho e memória reduzidos e cobertura de falhas similar a técnicas presentes na literatura. Como detecção é menos custoso que correção, este trabalho foca em técnicas de detecção. Primeiramente, um conjunto de técnicas de dados baseadas em regras de generalização, chamada VAR, é apresentada. As técnicas são baseadas nesse conjunto generalizado de regras para permitir uma investigação exaustiva, em termos de confiabilidade e custos, de diferentes variações de técnicas. As regras definem como a técnica duplica o código e insere verificadores. Cada técnica usa um diferente conjunto de regras. Então, uma técnica de controle, chamada SETA, é introduzida. Comparando SETA com uma técnica estado-da-arte, SETA é 11.0% mais rápida e ocupa 10.3% menos posições de memória. As técnicas de dados mais promissoras são combinadas com a técnica de controle com o objetivo de proteger tanto os dados quanto o fluxo de controle da aplicação alvo. Para reduzir ainda mais os custos, métodos para aplicar seletivamente as técnicas propostas foram desenvolvidos. Para técnica de dados, em vez de proteger todos os registradores, somente um conjunto de registradores selecionados é protegido. O conjunto é selecionado com base em uma métrica que analisa o código e classifica os registradores por sua criticalidade. Para técnicas de controle, há duas abordagens: (1) remover verificadores de blocos básicos, e (2) seletivamente proteger blocos básicos. As técnicas e suas versões seletivas são avaliadas em termos de tempo de execução, tamanho do código, cobertura de falhas, e o Mean Work to Failure (MWTF), o qual é uma métrica que mede o compromisso entre cobertura de falhas e tempo de execução. Resultados mostram redução dos custos sem diminuição da cobertura de falhas, e para uma pequena redução na cobertura de falhas foi possível significativamente reduzir os custos. Por fim, uma vez que a avaliação de todas as possíveis combinações utilizando métodos seletivos toma muito tempo, este trabalho utiliza um método para extrapolar os resultados obtidos por simulação com o objetivo de encontrar os melhores parâmetros para a proteção seletiva e combinada de técnicas de dados e de controle que melhorem o compromisso entre confiabilidade e custos. / Software-based fault tolerance techniques are a low-cost way to protect processors against soft errors. However, they introduce significant overheads to the execution time and code size, which consequently increases the energy consumption. System operation with time or energy restrictions may not be able to make use of these techniques. For this reason, this work proposes software-based fault tolerance techniques with lower overheads and similar fault coverage to state-of-the-art software techniques. Once detection is less costly than correction, the work focuses on software-based detection techniques. Firstly, a set of data-flow techniques called VAR is proposed. The techniques are based on general building rules to allow an exhaustive assessment, in terms of reliability and overheads, of different technique variations. The rules define how the technique duplicates the code and insert checkers. Each technique uses a different set of rules. Then, a control-flow technique called SETA (Software-only Error-detection Technique using Assertions) is introduced. Comparing SETA with a state-of-the-art technique, SETA is 11.0% faster and occupies 10.3% fewer memory positions. The most promising data-flow techniques are combined with the control-flow technique in order to protect both dataflow and control-flow of the target application. To go even further with the reduction of the overheads, methods to selective apply the proposed software techniques have been developed. For the data-flow techniques, instead of protecting all registers, only a set of selected registers is protected. The set is selected based on a metric that analyzes the code and rank the registers by their criticality. For the control-flow technique, two approaches are taken: (1) removing checkers from basic blocks: all the basic blocks are protected by SETA, but only selected basic blocks have checkers inserted, and (2) selectively protecting basic blocks: only a set of basic blocks is protected. The techniques and their selective versions are evaluated in terms of execution time, code size, fault coverage, and Mean Work To Failure (MWTF), which is a metric to measure the trade-off between fault coverage and execution time. Results show that was possible to reduce the overheads without affecting the fault coverage, and for a small reduction in the fault coverage it was possible to significantly reduce the overheads. Lastly, since the evaluation of all the possible combinations for selective hardening of every application takes too much time, this work uses a method to extrapolate the results obtained by simulation in order to find the parameters for the selective combination of data and control-flow techniques that are probably the best candidates to improve the trade-off between reliability and overheads.

Detectores de falhas não confiáveis tradicionais são oráculos disponíveis localmente para processos deumsistema distribuído que fornecem uma lista de processos suspeitos de terem falhado. Este trabalho propõe um novo e flexível detector de falhas não confiável, chamado Impact FD, que fornece como saída um valor trust level que é o grau de confiança no sistema. Ao expressar a relevância de cada processo por um valor de fator de impacto, bem como por uma margem de falhas aceitáveis do sistema, o Impact FD permite ao usuário ajustar a configuração do detector de falhas de acordo com os requisitos da aplicação: em certos cenários, o defeito de umprocesso de baixo impacto ou redundante não compromete a confiança no sistema, enquanto o defeito de um processo de alto fator de impacto pode afetá-la seriamente. Assim, pode ser adotada uma estragégia de monitoramento com maior ou menor rigor. Em particular, definimos algumas propriedades de flexibilidade que caracterizam a capacidade do Impact FD para tolerar uma certa margem de falhas ou falsas suspeitas, ou seja, a sua capacidade de fornecer diferentes conjuntos de respostas que levam o sistema a estados confiáveis. O Impact FD é adequado para sistemas que apresentam redundância de nodos, heterogeneidade de nodos, recurso de agrupamento e permite uma margem de falhas que não degrada a confiança no sistema. Nós também mostramos que algumas classes do Impact FD são equivalentes a § e ­, que são detectores de falhas fundamentais para contornar a impossibilidade de resolver o problema do consenso em sistemas de transmissão de mensagens assíncronas na presença de falhas. Adicionalmente, com base em pressupostos de sincronia e nas abordagens baseada em tempo e padrão de mensagem, apresentamos três algoritmos que implementam o Impact FD. Os resultados da avaliação de desempenho usando traces reais do PlanetLab confirmam o grau de aplicabilidade flexível do nosso detector de falhas e, devido à margem aceitável de falhas, o número de falsas respostas ou suspeitas pode ser tolerado quando comparado a tradicionais detectores de falhas não confiáveis. / Traditional unreliable failure detectors are per process oracles that provide a list of processes suspected of having failed. This work proposes a new and flexible unreliable failure detector (FD), denoted the Impact FD, that outputs a trust level value which is the degree of confidence in the system. By expressing the relevance of each process by an impact factor value as well as a margin of acceptable failures of the system, the Impact FD enables the user to tune the failure detection configuration in accordance with the requirements of the application: in some scenarios, the failure of low impact or redundant processes does not jeopardize the confidence in the system, while the crash of a high impact process may seriously affect it. Either a softer or stricter monitoring strategy can be adopted. In particular, we define some flexibility properties that characterize the capacity of the Impact FD to tolerate a certain margin of failures or false suspicions, i.e., its capacity of providing different sets of responses that lead the system to trusted states. The Impact FD is suitable for systems that present node redundancy, heterogeneity of nodes, clustering feature, and allow a margin of failures which does not degrade the confidence in the system. We also show that some classes of the Impact FD are equivalent to ­ and § which are fundamental FDs to circumvent the impossibility of solving the consensus problem in asynchronous message-passing systems in presence of failures. Additionally, based on different synchrony assumptions and message-pattern or timer-based approaches, we present three algorithms which implement the Impact FD. Performance evaluation results using real PlanetLab traces confirmthe degree of flexible applicability of our failure detector and, due to the accepted margin of failures, that false responses or suspicions may be tolerated when compared to traditional unreliable failure detectors.

Esta dissertação aborda um ramo da computação que se encontra em crescente desenvolvimento: a computação em tempo real. Os sistemas de computação tempo real surgiram a partir da necessidade de substituição do controle humano, que muitas vezes é falho, em situações complexas ou críticas, onde máxima confiabilidade e disponibilidade são exigidas para garantir a segurança do sistema. A área de aplicação diferencia-se de outras convencionais por possuir diferentes tipos de restrições de tempo e operar em ambientes não-determinísticos. Entretanto, atualmente tais sistemas estão tornando-se grandes, complexos, distribuídos, adaptativos e cada vez mais presentes nas aplicações do dia-a-dia,o que tende a exigir soluções mais simples e generalizadas. Pelo fato de tais sistemas normalmente atuarem sobre aplicações críticas, importante salientar que, em algumas situações, pequenos erros no sistema podem levar a grandes catástrofes. Mesmo atrasos mínimos no tempo de resposta são problemáticos, podendo ocasionar degradações ou ações erradas no mundo físico controlado pelo sistema tempo real. Como nestes casos máxima confiabilidade e disponibilidade são exigidas para garantir a sua segurança, tornou-se importante a construção de sistemas tempo real tolerantes a falhas. Dessa forma, é visivelmente crescente a necessidade de utilização de mecanismos capazes de abordar os requisitos de tempo real e tolerância a falhas de forma integrada durante o desenvolvimento do sistema. Assim, o processo de desenvolvimento de sistemas tempo real confiáveis torna-se mais simples e mais eficiente. A necessidade de maior conhecimento do uso de tolerância a falhas para obter segurança no funcionamento de aplicações tempo real levou ao desenvolvimento deste trabalho, onde buscou-se um caminho de solução para a adequação das técnicas de tolerância a falhas a estas aplicações. Sabe-se que para produzir software confiável e, desta forma de maior qualidade, além do emprego de boas técnicas de engenharia de software, é necessário compreender os principais conceitos e técnicas de tolerância a falhas. Por outro lado, é importante ter-se conhecimento dos mecanismos oferecidos pelas diversas camadas de software de um sistema - protocolo de comunicação, sistema operacional e linguagem de programação - para apoiar estas atividades de tolerância a falhas. Este trabalho busca analisar os mecanismos e técnicas usados na implementação de software tolerante a falhas frente às situações mencionadas, uma vez que nem todas as técnicas conhecidas podem ser indistintamente aplicáveis a estas situações. Os resultados desta análise são organizados na forma de uma taxonomia, visando assim auxiliar projetistas de desenvolvimento de software a tomarem decisões importantes na construção de sistemas tempo real tolerantes a falhas. Os mecanismos são agrupados de acordo com o nível de implementação: sistemas operacionais, linguagens de programação e protocolos de comunicação, destacando suas características e aplicabilidade. Por fim uso da classificação é demonstrado com a análise de três casos-exemplo. / This dissertation is about a, computer science field which is in growing development, that is, real-time computation. Real-time computing systems have emerged from the necessity of substituting. human control which is sometimes failed in complex or critical situations. In these ones maximum availability and reliability are requested in order to guarantee the system dependability. The application area differs from the conventional ones because it has particular time constraints and operates in nondeterministic environments. Nevertheless, nowadays such systems are becoming large, complex, distributed and adaptive but tend to demand simpler and generalized solutions as they are more present in daily applications. Since such systems normally act on critical applications it is important to reinforce, that in some situations, subtle systems errors may generate big catastrophes. Even slight delays in response time are troublesome and they may cause degradation or wrong acts in physical world controlled by real-time systems. In these cases maximum reliability and availability are requested in order to guarantee system dependability. Thereby, the requirement of including mechanisms capable of achieving real-time and fault tolerance in an integrated way during the system design has been increased. Thus, the developing process of reliable real-time systems becomes simpler and more effective. The necessity of improving designers knowledge on using fault tolerance in order to obtain dependability on real-time applications has motivated this study. Our main goal has been to find an adequate way of using fault tolerance techniques to these applications. It is known that the development of reliable software not only requires appropriate software engineering techniques but also demands understanding of main politics and mechanisms used to implement fault tolerance techniques in these situations. Otherwise, it is very important to know the related support that is offered by the different software levels of a system - communication protocol, operating system and programming language. This study has as purpose analyzing the mechanisms and techniques used in implementation of fault-tolerant software applied to the previously mentioned situations. The basic supposition is that not all the known techniques may be applied indistinctly to these situations. The properties of the software are organized according to a taxonomy, where the mechanisms are bracketed in groups according to implementation level: operating systems, programming languages and communication protocols. In this presentation, the characteristics and applicability of the software tools are stood out in order to help developing-software designers to decide what is important to build faulttolerant software. Finally, the use of the classification is demonstrated by analyzing three case-examples.

Os circuitos integrados recentes baseados em tecnologias nanoeletrônicas estão significativamente mais vulneráveis a falhas transientes. Os erros gerados são assim também mais críticos do que eram antes. Esta tese apresenta uma nova virtude em termos de confiabilidade dos circuitos assíncronos quase-insensíveis aos atrasos (QDI): a sua grande habilidade natural para mitigar falhas transientes de longa duração, que são severas em circuitos síncronos modernos. Uma metodologia para avaliar comparativamente os efeitos de falhas transientes tanto em circuitos síncronos como em circuitos assíncronos QDI é apresentada. Além disso, um método para obter a habilidade de mitigação de falhas transientes dos elementos de memória de circuitos QDI (ou seja, os C-elements) é também proposto. Por fim, técnicas de mitigação são sugeridas para aumentar ainda mais a atenuação de falhas transientes por parte dos Celements e, por consequência, também a robustez dos sistemas assíncronos QDI. / Recent deep-submicron technology-based ICs are significantly more vulnerable to transient faults. The arisen errors are thus also more critical than they have ever been before. This thesis presents a further novel benefit of the Quasi-Delay Insensitive (QDI) asynchronous circuits in terms of reliability: their strong natural ability to mitigate longduration transient faults that are severe in modern synchronous circuits. A methodology to evaluate comparatively the transient-fault effects on synchronous and QDI asynchronous circuits is presented. Furthermore, a method to obtain the transient-fault mitigation ability of the QDI circuits’ memory elements (i.e., the C-elements) is also proposed. Finally, mitigation techniques are suggested to increase even more the Celements’ transient-fault attenuation, and thus also the QDI asynchronous systems’ robustness.

Detectores de falhas não confiáveis tradicionais são oráculos disponíveis localmente para processos deumsistema distribuído que fornecem uma lista de processos suspeitos de terem falhado. Este trabalho propõe um novo e flexível detector de falhas não confiável, chamado Impact FD, que fornece como saída um valor trust level que é o grau de confiança no sistema. Ao expressar a relevância de cada processo por um valor de fator de impacto, bem como por uma margem de falhas aceitáveis do sistema, o Impact FD permite ao usuário ajustar a configuração do detector de falhas de acordo com os requisitos da aplicação: em certos cenários, o defeito de umprocesso de baixo impacto ou redundante não compromete a confiança no sistema, enquanto o defeito de um processo de alto fator de impacto pode afetá-la seriamente. Assim, pode ser adotada uma estragégia de monitoramento com maior ou menor rigor. Em particular, definimos algumas propriedades de flexibilidade que caracterizam a capacidade do Impact FD para tolerar uma certa margem de falhas ou falsas suspeitas, ou seja, a sua capacidade de fornecer diferentes conjuntos de respostas que levam o sistema a estados confiáveis. O Impact FD é adequado para sistemas que apresentam redundância de nodos, heterogeneidade de nodos, recurso de agrupamento e permite uma margem de falhas que não degrada a confiança no sistema. Nós também mostramos que algumas classes do Impact FD são equivalentes a § e ­, que são detectores de falhas fundamentais para contornar a impossibilidade de resolver o problema do consenso em sistemas de transmissão de mensagens assíncronas na presença de falhas. Adicionalmente, com base em pressupostos de sincronia e nas abordagens baseada em tempo e padrão de mensagem, apresentamos três algoritmos que implementam o Impact FD. Os resultados da avaliação de desempenho usando traces reais do PlanetLab confirmam o grau de aplicabilidade flexível do nosso detector de falhas e, devido à margem aceitável de falhas, o número de falsas respostas ou suspeitas pode ser tolerado quando comparado a tradicionais detectores de falhas não confiáveis. / Traditional unreliable failure detectors are per process oracles that provide a list of processes suspected of having failed. This work proposes a new and flexible unreliable failure detector (FD), denoted the Impact FD, that outputs a trust level value which is the degree of confidence in the system. By expressing the relevance of each process by an impact factor value as well as a margin of acceptable failures of the system, the Impact FD enables the user to tune the failure detection configuration in accordance with the requirements of the application: in some scenarios, the failure of low impact or redundant processes does not jeopardize the confidence in the system, while the crash of a high impact process may seriously affect it. Either a softer or stricter monitoring strategy can be adopted. In particular, we define some flexibility properties that characterize the capacity of the Impact FD to tolerate a certain margin of failures or false suspicions, i.e., its capacity of providing different sets of responses that lead the system to trusted states. The Impact FD is suitable for systems that present node redundancy, heterogeneity of nodes, clustering feature, and allow a margin of failures which does not degrade the confidence in the system. We also show that some classes of the Impact FD are equivalent to ­ and § which are fundamental FDs to circumvent the impossibility of solving the consensus problem in asynchronous message-passing systems in presence of failures. Additionally, based on different synchrony assumptions and message-pattern or timer-based approaches, we present three algorithms which implement the Impact FD. Performance evaluation results using real PlanetLab traces confirmthe degree of flexible applicability of our failure detector and, due to the accepted margin of failures, that false responses or suspicions may be tolerated when compared to traditional unreliable failure detectors.

A utilização de técnicas de tolerância a falhas em software é uma forma de baixo custo para proteger processadores contra soft errors. Contudo, elas causam aumento no tempo de execução e utilização de memória. Em consequência disso, o consumo de energia também aumenta. Sistemas que operam com restrição de tempo ou energia podem ficar impossibilitados de utilizar tais técnicas. Por esse motivo, este trabalho propoe técnicas de tolerância a falhas em software com custos no desempenho e memória reduzidos e cobertura de falhas similar a técnicas presentes na literatura. Como detecção é menos custoso que correção, este trabalho foca em técnicas de detecção. Primeiramente, um conjunto de técnicas de dados baseadas em regras de generalização, chamada VAR, é apresentada. As técnicas são baseadas nesse conjunto generalizado de regras para permitir uma investigação exaustiva, em termos de confiabilidade e custos, de diferentes variações de técnicas. As regras definem como a técnica duplica o código e insere verificadores. Cada técnica usa um diferente conjunto de regras. Então, uma técnica de controle, chamada SETA, é introduzida. Comparando SETA com uma técnica estado-da-arte, SETA é 11.0% mais rápida e ocupa 10.3% menos posições de memória. As técnicas de dados mais promissoras são combinadas com a técnica de controle com o objetivo de proteger tanto os dados quanto o fluxo de controle da aplicação alvo. Para reduzir ainda mais os custos, métodos para aplicar seletivamente as técnicas propostas foram desenvolvidos. Para técnica de dados, em vez de proteger todos os registradores, somente um conjunto de registradores selecionados é protegido. O conjunto é selecionado com base em uma métrica que analisa o código e classifica os registradores por sua criticalidade. Para técnicas de controle, há duas abordagens: (1) remover verificadores de blocos básicos, e (2) seletivamente proteger blocos básicos. As técnicas e suas versões seletivas são avaliadas em termos de tempo de execução, tamanho do código, cobertura de falhas, e o Mean Work to Failure (MWTF), o qual é uma métrica que mede o compromisso entre cobertura de falhas e tempo de execução. Resultados mostram redução dos custos sem diminuição da cobertura de falhas, e para uma pequena redução na cobertura de falhas foi possível significativamente reduzir os custos. Por fim, uma vez que a avaliação de todas as possíveis combinações utilizando métodos seletivos toma muito tempo, este trabalho utiliza um método para extrapolar os resultados obtidos por simulação com o objetivo de encontrar os melhores parâmetros para a proteção seletiva e combinada de técnicas de dados e de controle que melhorem o compromisso entre confiabilidade e custos. / Software-based fault tolerance techniques are a low-cost way to protect processors against soft errors. However, they introduce significant overheads to the execution time and code size, which consequently increases the energy consumption. System operation with time or energy restrictions may not be able to make use of these techniques. For this reason, this work proposes software-based fault tolerance techniques with lower overheads and similar fault coverage to state-of-the-art software techniques. Once detection is less costly than correction, the work focuses on software-based detection techniques. Firstly, a set of data-flow techniques called VAR is proposed. The techniques are based on general building rules to allow an exhaustive assessment, in terms of reliability and overheads, of different technique variations. The rules define how the technique duplicates the code and insert checkers. Each technique uses a different set of rules. Then, a control-flow technique called SETA (Software-only Error-detection Technique using Assertions) is introduced. Comparing SETA with a state-of-the-art technique, SETA is 11.0% faster and occupies 10.3% fewer memory positions. The most promising data-flow techniques are combined with the control-flow technique in order to protect both dataflow and control-flow of the target application. To go even further with the reduction of the overheads, methods to selective apply the proposed software techniques have been developed. For the data-flow techniques, instead of protecting all registers, only a set of selected registers is protected. The set is selected based on a metric that analyzes the code and rank the registers by their criticality. For the control-flow technique, two approaches are taken: (1) removing checkers from basic blocks: all the basic blocks are protected by SETA, but only selected basic blocks have checkers inserted, and (2) selectively protecting basic blocks: only a set of basic blocks is protected. The techniques and their selective versions are evaluated in terms of execution time, code size, fault coverage, and Mean Work To Failure (MWTF), which is a metric to measure the trade-off between fault coverage and execution time. Results show that was possible to reduce the overheads without affecting the fault coverage, and for a small reduction in the fault coverage it was possible to significantly reduce the overheads. Lastly, since the evaluation of all the possible combinations for selective hardening of every application takes too much time, this work uses a method to extrapolate the results obtained by simulation in order to find the parameters for the selective combination of data and control-flow techniques that are probably the best candidates to improve the trade-off between reliability and overheads.

Os circuitos integrados recentes baseados em tecnologias nanoeletrônicas estão significativamente mais vulneráveis a falhas transientes. Os erros gerados são assim também mais críticos do que eram antes. Esta tese apresenta uma nova virtude em termos de confiabilidade dos circuitos assíncronos quase-insensíveis aos atrasos (QDI): a sua grande habilidade natural para mitigar falhas transientes de longa duração, que são severas em circuitos síncronos modernos. Uma metodologia para avaliar comparativamente os efeitos de falhas transientes tanto em circuitos síncronos como em circuitos assíncronos QDI é apresentada. Além disso, um método para obter a habilidade de mitigação de falhas transientes dos elementos de memória de circuitos QDI (ou seja, os C-elements) é também proposto. Por fim, técnicas de mitigação são sugeridas para aumentar ainda mais a atenuação de falhas transientes por parte dos Celements e, por consequência, também a robustez dos sistemas assíncronos QDI. / Recent deep-submicron technology-based ICs are significantly more vulnerable to transient faults. The arisen errors are thus also more critical than they have ever been before. This thesis presents a further novel benefit of the Quasi-Delay Insensitive (QDI) asynchronous circuits in terms of reliability: their strong natural ability to mitigate longduration transient faults that are severe in modern synchronous circuits. A methodology to evaluate comparatively the transient-fault effects on synchronous and QDI asynchronous circuits is presented. Furthermore, a method to obtain the transient-fault mitigation ability of the QDI circuits’ memory elements (i.e., the C-elements) is also proposed. Finally, mitigation techniques are suggested to increase even more the Celements’ transient-fault attenuation, and thus also the QDI asynchronous systems’ robustness.