Made available in DSpace on 2014-06-12T15:54:42Z (GMT). No. of bitstreams: 2 arquivo7293_1.pdf: 1302559 bytes, checksum: 5c29fcb5cfb2253f5a91930260887780 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / Um sistema distribuído pode ser definido como um conjunto de processos que se comunicam através de canais de comunicação. Modelos para sistemas distribuídos determinam características do funcionamento destes sistemas, em especial com relação a aspectos temporais e de confiabilidade. O resultado da impossibilidade de se obter o consenso nos sistemas distribuídos assíncronos (modelo assíncrono), tolerando falhas, mesmo que apenas um processo possa falhar de forma silenciosa, estimulou o desenvolvimento de diversos modelos parcialmente síncronos de sistemas distribuídos. Estes modelos assumem algumas características síncronas, com o objetivo de evitar esta impossibilidade. Por outro lado, as novas arquiteturas para prover extit{QoS} são utilizadas para construir ambientes de execução híbridos, nos quais é possível fornecer serviços de comunicação com características síncronas para alguns canais de comunicação. O desafio que se apresenta é o de desenvolver um modelo para sistemas distribuídos adequado a executar em um ambiente equipado com arquiteturas para prover extit{QoS}. Este modelo deve considerar os aspectos síncronos e assíncronos do ambiente de execução, e ser adaptável às alterações dinâmicas que são características de arquiteturas para prover extit{QoS}. Nós respondemos a este desafio apresentando um novo modelo híbrido e adaptativo para sistemas distribuídos parcialmente síncronos, que é adaptável a alterações no estado do ambiente de execução, comuns em ambientes de execução com extit{QoS} cite{modelo,dsn2002,wtdladc2003,wtf2004,tecreportmodelo,sbrc2005}. Este modelo é híbrido ao assumir a coexistência de processos com características síncronas e assíncronas. O modelo apresentado também permite que os processos alterem o seu estado dinamicamente, sem prejuízo para a consistência dos sistemas em execução. Foi desenvolvida uma implementação do modelo proposto baseada em um ambiente de execução com extit{QoS}. Para viabilizar a execução desta implementação, foi desenvolvida uma infra-estrutura de comunicação, a qual denominamos QoS Provider, (QoSP), cujo objetivo principal é gerar uma interface padrão entre o nosso modelo e arquiteturas para prover extit{QoS} existentes. Um novo protocolo de consenso para o modelo de sistemas distribuídos proposto é apresentado nesta tese. Este protocolo de consenso apresenta resultados ótimos com relação à tolerância a falhas em sistemas parcialmente síncronos (tolera $f < n$ falhas de processos em algumas situações), e a complexidade (apresenta um limite inferior de dois passos de comunicação, resultado mínimo para o consenso em sistemas parcialmente síncronos). Foram realizados experimentos com o consenso, que comprovaram o bom desempenho deste protocolo, associado a uma tolerância a falhas ajustada ao nível de sincronismo representado no modelo

The technological advances resulting from electronic systems miniaturization were crucial to the reach of current technology. The microelectronics and studies to reduce power consumption in electronic devices provided that mobile sensor networks become increasingly used. A mobile sensor network is composed of several sensors nodes, which work collaboratively to achieve a certain goal. Each network node has layers and applications for specific purposes, two of the most important algorithms present in most applications in sensor networks are failure detectors and localization algorithms. Failure detectors are algorithms that check faulty nodes in the network by exchanging messages. This algorithm is a fundamental block in distributed applications and fault tolerant. Moreover, the localization algorithm is an alternative to GPS use. Using the content of messages transmitted by nodes, the algorithm computes a location coordinates of the node from a reference point. Several methodologies have been proposed in literature for both algorithms. However, even with functional similarities are not found searches uniting these algorithms in one in order to save resources and improve efficiency in wireless sensor networks. This study proposes a hybrid method in which the failure detector takes advantage of messages sent by localization algorithm to perform its task. This solution optimizes the messages exchange sent by nodes, reducing the transmission of data packets. As result, the solution reduces the power consumption of nodes and improves system performance. / Os avanços tecnológicos decorrentes da miniaturização de sistemas eletrônicos nas últimas décadas foram determinantes para o alcanço da tecnologia atual. A microeletrônica, em conjunto com estudos de redução de consumo de energia em dispositivos eletrônicos, propiciou que as redes de sensores móveis se difundissem rapidamente ao redor do mundo. Uma rede de sensores móveis é composta por diversos nodos sensores, que trabalham colaborativamente para alcançar um determinado objetivo. Cada nodo da rede possui camadas e aplicações com fins específicos, dois dos mais importantes algoritmos presentes na maioria das aplicações em redes de sensores são os detectores de defeitos e os algoritmos de localização. Os detectores de defeitos são algoritmos que normalmente são executados na camada de aplicação e seu objetivo é detectar através da troca de mensagem entre eles possíveis nodos falhos na rede. O algoritmo detector de defeitos é bloco fundamental em aplicações distribuídas e tolerantes a falhas. Por outro lado, o algoritmo de localização é uma proposta alternativa a utilização do GPS. Por meio da troca de mensagem entre os nodos, a partir de um ponto de referência o algoritmo de localização calcula as coordenadas do nodo no espaço. Diversas metodologias já foram propostas na bibliografia para ambos os algoritmos. Porém, mesmo com similaridades funcionais, não são encontradas pesquisas que integrem estes algoritmos, a fim de economizar recursos e melhorar a eficiência das redes de sensores. Este trabalho propõe um método híbrido em que o detector de defeitos aproveita a troca de mensagens realizada pelo algoritmo de localização para realizar sua tarefa. A solução aperfeiçoa a troca de mensagens enviadas pelos nodos, evitando o envio de pacotes de dados. Como resultado, a solução diminui o consumo de energia dos nodos e melhora o desempenho do sistema.

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