Este trabalho relata observações e analises sobre como os detectores de defeitos influenciam as operação de consenso. O conceito dos detectores de defeitos é essencial para as operações de consenso em sistemas distribuídos assíncronos, uma vez que esses representam uma das (micas formas de sobrepujar as limitações impostas pela chamada Impossibilidade FLP (impossibilidade de diferenciar um processo falho de um processo mais lento). Enquanto os detectores de defeitos tem seu funcionamento bem definido através de duas propriedades, completeness e accuracy, Não há nenhuma restrição quanto a forma de implementá-los. Na literatura são encontrados vários modelos de detectores de defeitos, construídos com as mais variadas estratégias, mecanismos de comunicação e de detecção. No entanto, estes modelos não costumam ser acompanhados de uma comparação com os detectores já existentes; os autores limitam-se a apresentar as inovações dos mecanismos sugeridos. De toda literatura pesquisada, apenas um trabalho procurou comparar diferentes modelos de detectores de defeitos, e através de simulações, avaliou o impacto destes detectores sobre o tempo de terminação das operações de consenso. Entretanto, aquele trabalho era bem limitado, tanto nos modelos de detectores analisados quanto nos objetivos das observações. O presente trabalho procurou estender aquele experimento, incluindo mais modelos de detectores, e transportando-os para um ambiente prático de execução. As observações realizadas não ficaram limitadas as avaliações já realizadas por aquele trabalho, de tal forma que os modelos de detectores testados foram analisados sob diversas métricas, situações e parâmetros de operação. Essas avaliações possibilitaram verificar o comportamento dos detectores frente aos padrões de falhas mais significativos, avaliar o impacto de cada detector sobre as operações de consenso e a sua interação com os elementos do ambiente de execução. Essas avaliações permitiram fazer uma comparação dos detectores, possibilitando a identificação de suas limitações, suas situações de melhor desempenho e possíveis otimizações para serem realizadas em trabalhos futuros. / This work presents our observations and analysis on the influence of the failure detectors on the consensus algorithm. Failure detectors are essential to the consensus over an asynchronous distributed system, as they represent one of the few techniques that are able to circumvent the limitation imposed by the FLP Impossibility (the impossibility to distinguish a crashed process from a slow one, in asynchronous systems). While failure detectors are well defined through two properties, completeness and accuracy, there's no rule about their implementation. Thus, in the literature there are many models of failure detectors, each one implemented using different approaches to the communication and detection strategies. However, these detectors seldom compare themselves to the existing ones; their authors usually present only the advantages and innovations of the new model. Indeed, we only found one work that tried to compare different failure detectors. Using simulation techniques, that work evaluated the impact of the failure detectors on the consensus termination time. However, that research was very limited in the number of detectors analyzed and in the evaluation goals. The present work extended that experience, including more detectors in the analysis and evaluating them in a practical environment. Also, the observations were not restricted to those from the original paper, and the detectors were analyzed with more metrics, failure patterns and operational parameters. The evaluation allowed us to identify the behavior from the detectors in face of the most significant failure patterns, their influence on the consensus operation and their interaction with the execution environment. These evaluation also enabled us to compare the detectors, identifying their limitations, their best employment situations and possible optimizations to future developments.

Este trabalho relata observações e analises sobre como os detectores de defeitos influenciam as operação de consenso. O conceito dos detectores de defeitos é essencial para as operações de consenso em sistemas distribuídos assíncronos, uma vez que esses representam uma das (micas formas de sobrepujar as limitações impostas pela chamada Impossibilidade FLP (impossibilidade de diferenciar um processo falho de um processo mais lento). Enquanto os detectores de defeitos tem seu funcionamento bem definido através de duas propriedades, completeness e accuracy, Não há nenhuma restrição quanto a forma de implementá-los. Na literatura são encontrados vários modelos de detectores de defeitos, construídos com as mais variadas estratégias, mecanismos de comunicação e de detecção. No entanto, estes modelos não costumam ser acompanhados de uma comparação com os detectores já existentes; os autores limitam-se a apresentar as inovações dos mecanismos sugeridos. De toda literatura pesquisada, apenas um trabalho procurou comparar diferentes modelos de detectores de defeitos, e através de simulações, avaliou o impacto destes detectores sobre o tempo de terminação das operações de consenso. Entretanto, aquele trabalho era bem limitado, tanto nos modelos de detectores analisados quanto nos objetivos das observações. O presente trabalho procurou estender aquele experimento, incluindo mais modelos de detectores, e transportando-os para um ambiente prático de execução. As observações realizadas não ficaram limitadas as avaliações já realizadas por aquele trabalho, de tal forma que os modelos de detectores testados foram analisados sob diversas métricas, situações e parâmetros de operação. Essas avaliações possibilitaram verificar o comportamento dos detectores frente aos padrões de falhas mais significativos, avaliar o impacto de cada detector sobre as operações de consenso e a sua interação com os elementos do ambiente de execução. Essas avaliações permitiram fazer uma comparação dos detectores, possibilitando a identificação de suas limitações, suas situações de melhor desempenho e possíveis otimizações para serem realizadas em trabalhos futuros. / This work presents our observations and analysis on the influence of the failure detectors on the consensus algorithm. Failure detectors are essential to the consensus over an asynchronous distributed system, as they represent one of the few techniques that are able to circumvent the limitation imposed by the FLP Impossibility (the impossibility to distinguish a crashed process from a slow one, in asynchronous systems). While failure detectors are well defined through two properties, completeness and accuracy, there's no rule about their implementation. Thus, in the literature there are many models of failure detectors, each one implemented using different approaches to the communication and detection strategies. However, these detectors seldom compare themselves to the existing ones; their authors usually present only the advantages and innovations of the new model. Indeed, we only found one work that tried to compare different failure detectors. Using simulation techniques, that work evaluated the impact of the failure detectors on the consensus termination time. However, that research was very limited in the number of detectors analyzed and in the evaluation goals. The present work extended that experience, including more detectors in the analysis and evaluating them in a practical environment. Also, the observations were not restricted to those from the original paper, and the detectors were analyzed with more metrics, failure patterns and operational parameters. The evaluation allowed us to identify the behavior from the detectors in face of the most significant failure patterns, their influence on the consensus operation and their interaction with the execution environment. These evaluation also enabled us to compare the detectors, identifying their limitations, their best employment situations and possible optimizations to future developments.

Este trabalho relata observações e analises sobre como os detectores de defeitos influenciam as operação de consenso. O conceito dos detectores de defeitos é essencial para as operações de consenso em sistemas distribuídos assíncronos, uma vez que esses representam uma das (micas formas de sobrepujar as limitações impostas pela chamada Impossibilidade FLP (impossibilidade de diferenciar um processo falho de um processo mais lento). Enquanto os detectores de defeitos tem seu funcionamento bem definido através de duas propriedades, completeness e accuracy, Não há nenhuma restrição quanto a forma de implementá-los. Na literatura são encontrados vários modelos de detectores de defeitos, construídos com as mais variadas estratégias, mecanismos de comunicação e de detecção. No entanto, estes modelos não costumam ser acompanhados de uma comparação com os detectores já existentes; os autores limitam-se a apresentar as inovações dos mecanismos sugeridos. De toda literatura pesquisada, apenas um trabalho procurou comparar diferentes modelos de detectores de defeitos, e através de simulações, avaliou o impacto destes detectores sobre o tempo de terminação das operações de consenso. Entretanto, aquele trabalho era bem limitado, tanto nos modelos de detectores analisados quanto nos objetivos das observações. O presente trabalho procurou estender aquele experimento, incluindo mais modelos de detectores, e transportando-os para um ambiente prático de execução. As observações realizadas não ficaram limitadas as avaliações já realizadas por aquele trabalho, de tal forma que os modelos de detectores testados foram analisados sob diversas métricas, situações e parâmetros de operação. Essas avaliações possibilitaram verificar o comportamento dos detectores frente aos padrões de falhas mais significativos, avaliar o impacto de cada detector sobre as operações de consenso e a sua interação com os elementos do ambiente de execução. Essas avaliações permitiram fazer uma comparação dos detectores, possibilitando a identificação de suas limitações, suas situações de melhor desempenho e possíveis otimizações para serem realizadas em trabalhos futuros. / This work presents our observations and analysis on the influence of the failure detectors on the consensus algorithm. Failure detectors are essential to the consensus over an asynchronous distributed system, as they represent one of the few techniques that are able to circumvent the limitation imposed by the FLP Impossibility (the impossibility to distinguish a crashed process from a slow one, in asynchronous systems). While failure detectors are well defined through two properties, completeness and accuracy, there's no rule about their implementation. Thus, in the literature there are many models of failure detectors, each one implemented using different approaches to the communication and detection strategies. However, these detectors seldom compare themselves to the existing ones; their authors usually present only the advantages and innovations of the new model. Indeed, we only found one work that tried to compare different failure detectors. Using simulation techniques, that work evaluated the impact of the failure detectors on the consensus termination time. However, that research was very limited in the number of detectors analyzed and in the evaluation goals. The present work extended that experience, including more detectors in the analysis and evaluating them in a practical environment. Also, the observations were not restricted to those from the original paper, and the detectors were analyzed with more metrics, failure patterns and operational parameters. The evaluation allowed us to identify the behavior from the detectors in face of the most significant failure patterns, their influence on the consensus operation and their interaction with the execution environment. These evaluation also enabled us to compare the detectors, identifying their limitations, their best employment situations and possible optimizations to future developments.

A comprehensive failure detection model is proposed to detect service failures in asynchronous distributed systems. The proposed model takes advantage of P2P technology to provide required functionality. When compared to similar studies in failure detection, the presented failure detection model is more autonomous in resolving service dependencies, embodies more flexibility in providing different failure detection functions (like unreliable failure detectors, membership services) and offers more security. A failure detection library is developed using JXTA P2P framework to show realization of such a model.

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

An unreliable failure detector is a basic building block widely used to implement fault tolerance techniques in asynchronous distributed systems. The use of failure detectors comes from the impossibility to implement deterministic agreement protocols in these environments, since it is not possible to distinguish a crashed process from a very slow process. However, the massive use of distributed computational resources claims for solutions applicable in large scale distributed systems. In these systers, traditional failure detector algorithms can present scalability problems, such as control message explosion problem, because a large number of messages could compromise the quality of service of failure detectors and the system scalability. The goal of this dissertation is minimize the problem of control message explosion generated by failure detector algorithms in large scale processes monitoring. To do that, we propose a new approach to reduce the number of control messages from reusing messages. Our approach explores the manipulation of the interrogation period or heartbeat period, maximizing the reuse of messages, and it is organized by two strategies: ATF (Frequency Rate Adaptation), that reuses failure detector messages to suppress control messages; and AMA (Reusing of Application Message), that reuses client application messages to suppress control messages. As result, the resulting approach is generic, in the sense that it could be applied to any failure detector algorithm, and practical, in the sense that for its, the traditional failure detectors algorithms need only to change the semantic of control messages. From our experimental results, we demonstrate that our approach reduces the number of control messages, minimizing the message explosion problem, without compromising the quality of service of the failure detector / Detectores de defeitos não con�áveis são amplamente utilizados como bloco básico na implementa ção de técnicas de tolerância a falhas em sistemas distribuídos assíncronos. Sua utilização nestes ambientes é motivada pela impossibilidade de implementação de protocolos de acordo determinísticos, pois não há como distinguir processos defeituosos daqueles de acesso mais lento. Entretanto, o uso maciço de recursos computacionais exige soluções aplicáveis a sistemas distribuídos de larga escala. Neste contexto, algoritmos tradicionais de detecção de defeitos podem apresentar problemas de escalabilidade, tal como o de explosão de mensagens. O grande número de mensagens enviadas pode comprometer a qualidade de serviço do detector de defeitos e a escalabilidade do sistema. Esta dissertação visa minimizar o problema da explosão de mensagens de controle geradas pelos algoritmos de detecção de defeitos em ações de monitoramento de processos. Para tal, propõe-se uma nova abordagem para redução do número de mensagens de controle através do reaproveitamento de mensagens. A abordagem explora a manipulação da periodicidade de envio das mensagens de controle, maximizando o reaproveitamento de mensagens, e é composta por duas estratégias: ATF (Adaptação da Taxa de Freqüência), a qual reaproveita mensagens dos próprios algoritmos de detecção para suprir mensagem de controle; e AMA (Aproveitamento de Mensagens da Aplicação), a qual reaproveita mensagens das aplicações clientes para o mesmo objetivo da ATF. Como resultado, têm-se uma abordagem genérica, no sentido que pode ser aplicada a qualquer algoritmo de detecção, e prática, no sentido que algoritmos tradicionais de detectores de defeitos necessitam apenas alterar a semântica das mensagens de controle para utilizá-la. Através de experimentos demonstra-se que sua aplicação reduz o número de mensagens de controle, minimizando o problema da explosão de mensagens, sem comprometer a qualidade de serviço do detector de defeitos