Protocolo de recuperação por retorno, coordenado, não determinístico

O uso da recuperação de processos para obter sistemas computacionais tolerantes a falhas não é um assunto novo. Entretanto, a discussão de algoritmos para a recuperação em sistemas distribuídos, notadamente aqueles que se enquadram na categoria assíncrona, ainda encontra pontos em aberto. Este é o contexto do presente trabalho. Este trabalho apresenta um novo algoritmo de recuperação por retorno, em sistemas distribuídos. O algoritmo proposto é do tipo coordenado, e seus mecanismos componentes determinam que seja classificado como um algoritmo baseado em índices (index-based coordinated). Desta forma, a tolerância a falhas é obtida através do estabelecimento de linhas de recuperação, o que possibilita um retorno consideravelmente rápido, em caso de falha. Seu desenvolvimento foi feito com o objetivo de minimizar o impacto ao desempenho do sistema, tanto quando este estiver operando livre de falhas como quando ocorrerem as falhas. Além disso, os mecanismos componentes do algoritmo foram escolhidos visando facilitar a futura tarefa de implementação. A satisfação dos objetivos decorre principalmente de uma importante característica assegurada pelos mecanismos propostos no algoritmo: o não bloqueio da aplicação, enquanto é estabelecida uma nova linha de recuperação. Esta característica, associada ao rápido retorno, oferece uma solução promissora, em termos de eficiência, para a recuperação, um vez que o impacto no desempenho tende a ser reduzido, quando o sistema encontra-se operando em ambas condições: livre de erros ou sob falha. Diferentemente da maioria dos algoritmos coordenados encontrados na literatura, o algoritmo proposto neste trabalho trata as mensagens perdidas. A partir da análise das características das aplicações, bem como dos canais de comunicação, quando estes interagem com o algoritmo de recuperação, concluiu-se que os procedimentos usados para recuperação de processos devem prever o tratamento desta categoria de mensagens. Assim, o algoritmo proposto foi incrementado com um mecanismo para tratamento das mensagens que têm o potencial de tornarem-se perdidas, em caso de retorno, ou seja, evita a existência de mensagens perdidas. Uma das decisões tomadas durante o desenvolvimento do algoritmo foi a de permitir um processamento não determinístico. Na realidade, esta escolha visou o aumento do espectro das falhas que poderiam ser tratadas pela recuperação. Tradicionalmente, a recuperação por retorno é empregada para tolerar falhas temporárias. Entretanto, a diversidade de ambiente, freqüente nos SDs, também pode ser usada para tolerar algumas falhas permanentes. Para verificar a correção do algoritmo, decidiu-se empregar um formalismo existente. Assim, a lógica temporal de Lamport (TLA) foi usada na especificação dos mecanismos do algoritmo bem como em sua demonstração de correção. O tratamento referente às mensagens perdidas, atrav´es do uso de mensagens de resposta, associado com o uso de uma lógica temporal, levou à necessidade de rever os critérios de consistência. Esta revisão gerou um conjunto de fórmulas de consistência ajustadas à existência de mensagens de diferentes classes: mensagens da aplicação e mensagens de resposta.

Uma proposta de arquitetura de um ambiente de desenvolvimento de software distribuído baseada em agentes

A crescente complexidade das aplicações, a contínua evolução tecnológica e o uso cada vez mais disseminado de redes de computadores têm impulsionado os estudos referentes ao desenvolvimento de sistemas distribuídos. Como estes sistemas não podem ser facilmente desenvolvidos com tecnologias de software tradicionais por causa dos limites destas em lidar com aspectos relacionados, por exemplo, à distribuição e interoperabilidade, a tecnologia baseada em agentes parece ser uma resposta promissora para facilitar o desenvolvimento desses sistemas, pois ela foi planejada para suportar estes aspectos, dentre outros. Portanto, é necessário também que a arquitetura dos ambientes de desenvolvimento de software (ADS) evolua para suportar novas metodologias de desenvolvimento que ofereçam o suporte necessário à construção de softwares complexos, podendo também estar integrada a outras tecnologias como a de agentes. Baseada nesse contexto, essa dissertação tem por objetivo apresentar a especificação de uma arquitetura de um ADS distribuído baseada em agentes (DiSEN – Distributed Software Engineering Environment). Esse ambiente deverá fornecer suporte ao desenvolvimento de software distribuído, podendo estar em locais geograficamente distintos e também os desenvolvedores envolvidos poderão estar trabalhando de forma cooperativa. Na arquitetura proposta podem ser identificadas as seguintes camadas: dinâmica, que será responsável pelo gerenciamento da (re)configuração do ambiente em tempo de execução; aplicação, que terá, entre os elementos constituintes, a MDSODI (Metodologia para Desenvolvimento de Software Distribuído), que leva em consideração algumas características identificadas em sistemas distribuídos, já nas fases iniciais do projeto e o repositório para armazenamento dos dados necessários ao ambiente; e, infra-estrutura, que proverá suporte às tarefas de nomeação, persistência e concorrência e incorporará o canal de comunicação. Para validar o ambiente será realizada uma simulação da comunicação que pode ser necessária entre as partes constituintes do DiSEN, por meio da elaboração de diagramas de use case e de seqüência, conforme a notação MDSODI. Assim, as principais contribuições desse trabalho são: (i) especificação da arquitetura de um ADS distribuído que poderá estar distribuído geograficamente; incorporará a MDSODI; proporcionará desenvolvimento distribuído; possuirá atividades executadas por agentes; (ii) os agentes identificados para o DiSEN deverão ser desenvolvidos obedecendo ao padrão FIPA (Foundation for Intelligent Physical Agents); (iii) a identificação de um elemento que irá oferecer apoio ao trabalho cooperativo, permitindo a integração de profissionais, agentes e artefatos.

FlexGroup: um ambiente flexível para comunicação em grupo

Mecanismos de comunicação entre processos são fundamentais no desenvolvimento de sistemas distribuídos, já que constituem o único meio de compartilhar dados entre processos que não dispõem de memória comum. Um dos principais mecanismos de comunicação utilizados é a troca de mensagens entre os processos componentes do sistema. Existem muitas aplicações que são compostas por um conjunto de processos que cooperam para realizar uma determinada tarefa e que são mais facilmente construídas se o sistema operacional oferecer a possibilidade de se enviar uma mensagem a diversos destinos. Neste caso são necessários mecanismos que permitam a difusão confiável de uma mensagem para um grupo de processos em uma única operação. Tendo em vista esta necessidade, diversos protocolos têm sido apresentados na literatura para permitir a comunicação entre um grupo de processos com diferentes graus de complexidade e de desempenho. Este trabalho apresenta um ambiente para desenvolvimento e utilização de protocolos de comunicação em grupo, denominado FlexGroup. O ambiente divide os protocolos em suas características fundamentais, permitindo que estas características possam ser desenvolvidas separadamente como subprotocolos. Os subprotocolo são interligados através de uma interface comum e gerenciados pelo núcleo do ambiente. A comunicação entre as diversas máquinas da rede é gerenciada pelo FlexGroup, permitindo que o desenvolvedor de um novo subprotocolo possa somente se focar nas características específicas do seu protocolo. Esta modularidade permite, ainda, que apenas as partes de interesse de um novo protocolo precisem ser implementadas, além de também viabilizar a criação de um protocolo baseado nos já existentes no ambiente. Além disso, o ambiente permite que as aplicações de comunicação em grupo possam definir, através de uma biblioteca, o conjunto de subprotocolos que desejam utilizar, em tempo de execução, sem necessidade de conhecer a implementação interna dos subprotocolos.. Da mesma forma, alguém que se proponha a realizar comparações com os protocolos existentes, pode utilizar os diversos subprotocolos e as aplicações existentes, bastando alterar os protocolos utilizados em tempo de execução e avaliando somente as características que deseje analisar.

Adaptação dinâmica do timeout de detectores de defeitos através do uso de séries temporais

Uma aplicação distribuída freqüentemente tem que ser especificada e implementada para executar sobre uma rede de longa distância (wide-área network-WAN), tipicamente a Internet. Neste ambiente, tais aplicações são sujeitas a defeitos do tipo colapso(falha geral num dado nó), teporização (flutuações na latência de comunicação) e omissão (perdas de mensagens). Para evitar que este defeitos gerem comseqüências indesejáveis e irreparáveis na aplicação, explora-se técnicas para tolerá-los. A abstração de detectores de defeitos não confiáveis auxilia a especificação e trato de algoritmos distribuídos utilizados em sistemas tolerantes a falhas, pois permite uma modelagem baseada na noção de estado (suspeito ou não suspeito) dos componentes (objetos, processo ou processadores) da aplicação. Para garantir terminação, os algoritmos de detecção de defeitos costumam utilizar a noção de limites de tempo de espera (timeout). Adicionalmente, para minimizar seu erro (falasas suspeitas) e não comprometer seu desempenho (tempo para detecção de um defeito), alguns detectores de defeitos ajustam dinamicamente o timeout com base em previsões do atraso de comunicação. Esta tese explora o ajuste dinâmico do timeout realizado de acordo com métodos de previsão baseados na teoria de séries temporais. Tais métodos supõem uma amostragem periódica e fornececm estimativas relativamente confiáveis do comportamento futuro da variável aleatória. Neste trabalho é especificado uma interface para transformar uma amostragem aperiódica do atraso de ida e volta de uma mensagem (rtt) numa amostragem periódica, é analisado comportamento de séries reais do rtt e a precisão dee sete preditores distintos (três baseados em séries temporais e quatrro não), e é avaliado a influência destes preditores na qualidade de serviço de um detector de defeitos do estilopull. Uma arquitetura orientada a objetos que possibilita a escolha/troca de algoritmos de previsão e de margem de segurança é também proposta. Como resultado, esta tese mostra: (i) que embora a amostragem do rtt seja aperiódica, pode-se modelá-la como sendo uma série temporal (uma amostragem periódica) aplciando uma interface de transformação; (ii) que a série temporal rtt é não estacionária na maioria dos casos de teste, contradizendo a maioria das hipóteses comumente consideradas em detectores de defeitos; (iii) que dentre sete modelos de predição, o modelo ARIMA (autoregressive integrated moving-average model) é o que oferece a melhor precisão na predição de atrasos de comunicação, em termos do erro quadrático médio: (iv) que o impacto de preditores baseados em séries temporais na qualidade de serviço do detector de defeitos não significativo em relação a modelos bem mais simples, mas varia dependendo da margem de segurança adotada; e (v) que um serviço de detecção de defeitos pode possibilitar a fácil escolha de algoritmos de previsão e de margens de segurança, pois o preditor pode ser modelado como sendo um módulo dissociado do detector.

Uma Abordagem de escalonamento adaptativo no ambiente Real-Time CORBA

CORBA vem se tornando o middleware padrão no desenvolvimento de aplicações distribuídas, tornando-as independentes de plataforma e linguagem. Ele tem sido utilizado também em aplicações de tempo real através de sua extensão para tempo real, o RT-CORBA. Apesar desta extensão ter conseguido reduzir vários dos problemas do CORBA no que se refere ao não-determinismo e falta de garantias temporais, ainda há muito estudo na área de mecanismos de escalonamento utilizados. Assim, este trabalho tem por objetivo apresentar uma proposta de escalonamento adaptativo no ambiente Real-Time CORBA. Nesta proposta o período das tarefas é controlado, variando dentro de uma faixa pré-estabelecida com o propósito de reduzir o atraso médio das tarefas da aplicação.

Um Modelo de replicação em ambientes que suportam mobilidade

Os estudos sobre mobilidade intensificaram-se com o uso em grande escala da Internet, pois esta trouxe a possibilidade de explorar mobilidade através de redes heterogêneas, conectadas por diferentes links de comunicação e distantes umas das outras. A replicação de componentes em sistemas distribuídos normalmente é utilizada para torná-los mais confiáveis e seguros ou para aumentar o desempenho da aplicação, uma vez que acessos remotos podem ser evitados através da localidade da réplica. Em qualquer um dos casos, a replicação implica a manutenção na consistência entre as múltiplas cópias, isto é, é preciso garantir que as cópias estejam com seus estados consistentes em um determinado momento. Em sistemas que permitem mobilidade e replicação, a principal preocupação é com a consistência e o gerenciamento das réplicas do objeto móvel. Isto é, dependendo da técnica de replicação utilizada, como gerenciar um objeto e suas réplicas se estes podem mudar sua localização? Como garantir um bom desempenho do sistema? Estas perguntas esta proposta procura responder. Este trabalho apresenta um modelo de replicação em ambientes de objetos distribuídos que permitem mobilidade chamado ReMMoS - Replication Model in Mobility Systems. O objetivo deste modelo é prover um ambiente de execução para suporte ao desenvolvimento de aplicações envolvendo mobilidade explicita e replicação implicita. Assim, o programador não necessita preocupar-se com o gerenciamento e a consistencia das cópias.

Avaliação de abordagens para captura de informações da aplicação

Numerosas pesquisas estão introduzindo o conceito de grupo em padrões abertos para programação distribuída. Nestas, o suporte a grupo de objetos por meio de middlewares, apresentam diferentes abordagens de interligação com a aplicação. Segundo princípios defendidos na tese de Felber, essas abordagens vão ao encontro do objetivo de facilitar o desenvolvimento e proporcionar confiabilidade e desempenho. Neste contexto, localizou-se três enfoques básicos para a interligação com a aplicação, denominados integração, serviço, e interceptação, que utilizam a captura de mensagens para obtenção de informações ou como meio para adicionar novas funcionalidades às aplicações. A utilização dessas informações pode auxiliar no ajuste de parâmetros funcionais de serviços relacionados, na escolha de mecanismos, influindo em aspectos como, desempenho e segurança. Ao longo do estudo dessas abordagens, sentiu-se a necessidade de estudar detalhes e testar aspectos de implementação, suas premissas de uso e as conseqüências advindas da incorporação de seus mecanismos junto à aplicação. Este trabalho visa apresentar uma análise do comportamento das referidas abordagens por meio da implementação de protótipos, possibilitando assim, investigar problemas relacionados ao emprego da técnica e suas conseqüências quando integradas à aplicação. Os objetivos específicos reúnem a busca de informações qualitativas, tais como: modularidade, transparência, facilidade de uso e portabilidade; e informações quantitativas, fundamentalmente traduzidas pelo grau de interferência no desempenho da aplicação. O desenvolvimento dos protótipos teve como início a busca por um ambiente que ofereceria suporte as condições necessárias para a implementação das diferentes abordagens. Percebeu-se que definir os mecanismos diretamente sobre uma linguagem de programação, como C ou C++, não era viável. As versões padrões dessas linguagens não oferecem mecanismos capazes de suportar algumas características de implementação como, por exemplo, a captura de mensagens na abordagem de interceptação. A possibilidade é introduzida apenas por extensões dessas linguagens. Assim, a investigação de um ambiente de implementação voltou-se para mecanismos disponíveis em sistemas operacionais. A opção pela utilização do Linux visou atender alguns requisitos importantes para o desenvolvimento dos protótipos tais como: facilidade de instalação, boa documentação e código aberto. Este último é um ponto essencial, pois a construção de parte dos protótipos explora a programação em nível do sistema operacional. A linguagem de programação C foi escolhida como base para a implementação, já que as diferentes abordagens exploram tanto o nível do kernel como o nível do usuário, e é compatível com o Linux. A etapa de desenvolvimento dos protótipos possibilitou a coleta de informações sobre aspectos qualitativos. As demais informações que fazem parte do perfil levantado por este trabalho sobre as abordagens, foram obtidas através da utilização dos protótipos em experimentos com duas aplicações distribuídas denominadas de “Ping-Pong” e “Escolha de Líderes”, que têm como característica geral à troca de mensagens, utilizando comunicação através de sockets. A realização de medidas em múltiplas execuções, avaliadas após o tratamento estatístico necessário, permitiu definir um perfil das diferentes abordagens.

Réplicas para alta disponibilidade em arquiteturas orientadas a componentes com suporte de comunicação de grupo

Alta disponibilidade é uma das propriedades mais desejáveis em sistemas computacionais, principalmente em aplicações comerciais que, tipicamente, envolvem acesso a banco de dados e usam transações. Essas aplicações compreendem sistemas bancários e de comércio eletrônico, onde a indisponibilidade de um serviço pode representar substanciais perdas financeiras. Alta disponibilidade pode ser alcançada através de replicação. Se uma das réplicas não está operacional, outra possibilita que determinado serviço seja oferecido. No entanto, réplicas requerem protocolos que assegurem consistência de estado. Comunicação de grupo é uma abstração que tem sido aplicada com eficiência a sistemas distribuídos para implementar protocolos de replicação. Sua aplicação a sistemas práticos com transações e com banco de dados não é comum. Tipicamente, sistemas transacionais usam soluções ad hoc e sincronizam réplicas com protocolos centralizados, que são bloqueantes e, por isso, não asseguram alta disponibilidade. A tecnologia baseada em componentes Enterprise JavaBeans (EJB) é um exemplo de sistema prático que integra distribuição, transações e bancos de dados. Em uma aplicação EJB, o desenvolvedor codifica o serviço funcional que é dependente da aplicação, e os serviços não–funcionais são inseridos automaticamente. A especificação EJB descreve serviços não–funcionais de segurança, de transações e de persistência para bancos de dados, mas não descreve serviços que garantam alta disponibilidade. Neste trabalho, alta disponibilidade é oferecida como uma nova propriedade através da adição de serviços não–funcionais na tecnologia EJB usando abstrações de comunicação de grupo. Os serviços para alta disponibilidade são oferecidos através da arquitetura HA (highly-available architecture) que possui múltiplas camadas. Esses serviços incluem replicação, chaveamento de servidor, gerenciamento de membros do grupo e detecção de membros falhos do grupo. A arquitetura HA baseia-se nos serviços já descritos pela especificação EJB e preserva os serviços EJB existentes. O protocolo de replicação corresponde a uma subcamada, invisível para o usuário final. O serviço EJB é executado por membros em um grupo de réplicas, permitindo a existência de múltiplos bancos de dados idênticos. Conflitos de acesso aos múltiplos bancos de dados são tratados estabelecendo–se uma ordem total para aplicação das atualizações das transações. Esse grupo é modelado como um único componente e gerenciado por um sistema de comunicação de grupo. A combinação de conceitos de bancos de dados com comunicação de grupo demonstra uma interessante solução para aplicações com requisitos de alta disponibilidade, como as aplicações EJB. Os serviços adicionais da arquitetura HA foram implementados em protótipo. A validação através de um protótipo possibilita que experimentos sejam realizados dentro de um ambiente controlado, usando diferentes cargas de trabalho sintéticas. O protótipo combina dois sistemas de código aberto. Essa característica permitiu acesso à implementação e não somente à interface dos componentes dos sistemas em questão. Um dos sistemas implementa a especificação EJB e outro implementa o sistema de comunicação de grupos. Os resultados dos testes realizados com o protótipo mostraram a eficiência da solução proposta. A degradação de desempenho pelo uso de réplicas e da comunicação de grupo é mantida em valores adequados.

Plataforma de comunicação tempo real sobre clusters SCI

Devido a sua baixa latência de banda, os clusters equipados com o adaptador SCI são uma alternativa para sistemas de tempo real distribuídos. Esse trabalho apresenta o projeto e implementação de uma plataforma de comunicação de tempo real sobre clusters SCI. O hardware padrão do SCI não se mostra adequado para a transmissão de tráfego de tempo real devido ao problema da contenção de acesso ao meio que causa inversão de prioridade. Por isso uma disciplina de acesso ao meio é implementada como parte da plataforma. Através da arquitetura implementada é possível o estabelecimento de canais de comunicação com garantia de banda. Assim, aplicações multimídias, por exemplo, podem trocar com taxa constante de conunicação. Cada mensagem é enviada somente uma vez. Assim, mensagens som a semântica de eventos podem ser enviadas. Além disso, a ordem e o tamanho das mensagens são garantidos. Além do tráfego com largura de banda garantida, a plataforma possibilita a troca de pacotes IP entre diferentes máquinas do cluster. Esses pacotes são inseridos no campo de dados dos pacotes próprios da plataforma e após são enviados através do uso de pacotes IP. Além disso, essa funcionalidade da plataforma permite também a execução de bibliotecas de comunicação baseadas em TCP/IP como o MPI sobre o cluster SCI. A plataforma de comunicação é implementada como modulos do sistema operacional Linux com a execução de tempo real RTAI. A valiação da plataforma mostrou que mesmo em cenários com muita comunicação entre todos os nodos correndo, a largura de banda reservada para cada canal foi mantida.

Implementação de recuperação por retorno de aplicações distribuídas baseada em checkpoints coordenados

A recuperação por retorno baseada em checkpointing é largamente usada como técnica de tolerância a falhas. O modelo complexo de sistemas distribuídos tem motivado o desenvolvimento de diversos algoritmos na tentativa de encontrar soluções mais simples e eficientes. Os processos que formam o sistema distribuído podem coordenar suas operações para garantir que o conjunto de checkpoints locais componha um estado global consistente (linha de recuperação). A partir desse estado, no caso de ocorrência de falhas, o sistema pode ser recuperado e a computação retomada a partir de um momento anterior ao da manifestação da falha, evitando o retrocesso para o estado inicial da computação e prevenindo a ocorrência de prejuízos com a perda de todo processamento até então realizado. No Grupo de Tolerância a Falhas da UFRGS foi proposto recentemente um algoritmo que é voltado para aplicações que executam em sistemas distribuídos assíncronos que se comunicam exclusivamente pela troca de mensagens. Ele opera com salvamento coordenado de checkpoints (não bloqueando as aplicações) e prevê o tratamento de mensagens órfãs e perdidas. Os mecanismos do algoritmo sugerem que nenhuma alteração deveria ser realizada no código das aplicações, criando a possibilidade de implementação transparente sob o ponto de vista dos usuários e dos programadores das aplicações. Como o algoritmo não requer o bloqueio das aplicações, a sobrecarga imposta pelos mecanismos à execução livre de falhas é pequena. Além disso, o processo de recuperação tende a ser efetuado rapidamente, uma vez que é garantida a existência de uma linha de recuperação consistente, facilmente identificada Este trabalho apresenta as decisões de projeto, a implementação, os resultados e a avaliação de desempenho desse algoritmo. A avaliação das alternativas de implementação resultou na decisão de uma implementação então realizada diretamente sobre o sistema operacional Linux, sem recorrer a protocolos auxiliares para garantir a execução dos serviços e sem a necessidade de adaptações no código das aplicações nem no código do sistema operacional. Adicionalmente, os resultados comprovaram a expectativa inicial de que o algoritmo causaria pouca sobrecarga no sistema (menos de 2%), embora ele ainda apresente alta dependência do tamanho dos checkpoints salvos.

Implementação de mecanismo de sincronismo virtual: experiência com Java

Este trabalho relata as atividades de estudo, projeto e implementação de uma aplicação distribuída que explora mecanismos básicos empregados em comunicação de grupo. O estudo é focado no desenvolvimento e uso dos conceitos de sincronismo virtual e em resultados aplicáveis para tolerância a falhas. O objetivo deste trabalho é o de demonstrar as repercussões práticas das principais características do modelo de sincronismo virtual no suporte à tolerância a falhas. São preceitos básicos os conceitos e primitivas de sistemas distribuídos utilizando troca de mensagens, bem como as alternativas de programação embasadas no conceito de grupos. O resultado final corresponde a um sistema Cliente/Servidor, desenvolvido em Java RMI, para simular um sistema distribuído com visões de grupo atualizadas em função da ocorrência de eventos significativos na composição dos grupos (sincronismo virtual). O sistema apresenta tratamento a falhas para o colapso (crash) de processos, inclusive do servidor (coordenador do grupo), e permite a consulta a dados armazenados em diferentes servidores. Foi projetado e implementado em um ambiente Windows NT, com protocolo TCP/IP. O resultado final corresponde a um conjunto de classes que pode ser utilizado para o controle da composição de grupos (membership). O aplicativo desenvolvido neste trabalho disponibiliza seis serviços, que são: inclusão de novos membros no grupo, onde as visões de todos os membros são atualizadas já com a identificação do novo membro; envio de mensagens em multicast aos membros participantes do grupo; envio de mensagens em unicast para um membro específico do grupo; permite a saída voluntária de membros do grupo, fazendo a atualização da visão a todos os membros do grupo; monitoramento de defeitos; e visualização dos membros participantes do grupo. Um destaque deve ser dado ao tratamento da suspeita de defeito do coordenador do grupo: se o mesmo sofrer um colapso, o membro mais antigo ativo é designado como o novo coordenador, e todos os membros do grupo são atualizados sobre a situação atual quanto à coordenação do grupo.

Communication Middleware for Distributed Hard Real-Time Systems in Java

Distributed real-time embedded systems are becoming increasingly important to society. More demands will be made on them and greater reliance will be placed on the delivery of their services. A relevant subset of them is high-integrity or hard real-time systems, where failure can cause loss of life, environmental harm, or significant financial loss. Additionally, the evolution of communication networks and paradigms as well as the necessity of demanding processing power and fault tolerance, motivated the interconnection between electronic devices; many of the communications have the possibility of transferring data at a high speed. The concept of distributed systems emerged as systems where different parts are executed on several nodes that interact with each other via a communication network. Java’s popularity, facilities and platform independence have made it an interesting language for the real-time and embedded community. This was the motivation for the development of RTSJ (Real-Time Specification for Java), which is a language extension intended to allow the development of real-time systems. The use of Java in the development of high-integrity systems requires strict development and testing techniques. However, RTJS includes a number of language features that are forbidden in such systems. In the context of the HIJA project, the HRTJ (Hard Real-Time Java) profile was developed to define a robust subset of the language that is amenable to static analysis for high-integrity system certification. Currently, a specification under the Java community process (JSR- 302) is being developed. Its purpose is to define those capabilities needed to create safety critical applications with Java technology called Safety Critical Java (SCJ). However, neither RTSJ nor its profiles provide facilities to develop distributed realtime applications. This is an important issue, as most of the current and future systems will be distributed. The Distributed RTSJ (DRTSJ) Expert Group was created under the Java community process (JSR-50) in order to define appropriate abstractions to overcome this problem. Currently there is no formal specification. The aim of this thesis is to develop a communication middleware that is suitable for the development of distributed hard real-time systems in Java, based on the integration between the RMI (Remote Method Invocation) model and the HRTJ profile. It has been designed and implemented keeping in mind the main requirements such as the predictability and reliability in the timing behavior and the resource usage. iThe design starts with the definition of a computational model which identifies among other things: the communication model, most appropriate underlying network protocols, the analysis model, and a subset of Java for hard real-time systems. In the design, the remote references are the basic means for building distributed applications which are associated with all non-functional parameters and resources needed to implement synchronous or asynchronous remote invocations with real-time attributes. The proposed middleware separates the resource allocation from the execution itself by defining two phases and a specific threading mechanism that guarantees a suitable timing behavior. It also includes mechanisms to monitor the functional and the timing behavior. It provides independence from network protocol defining a network interface and modules. The JRMP protocol was modified to include two phases, non-functional parameters, and message size optimizations. Although serialization is one of the fundamental operations to ensure proper data transmission, current implementations are not suitable for hard real-time systems and there are no alternatives. This thesis proposes a predictable serialization that introduces a new compiler to generate optimized code according to the computational model. The proposed solution has the advantage of allowing us to schedule the communications and to adjust the memory usage at compilation time. In order to validate the design and the implementation a demanding validation process was carried out with emphasis in the functional behavior, the memory usage, the processor usage (the end-to-end response time and the response time in each functional block) and the network usage (real consumption according to the calculated consumption). The results obtained in an industrial application developed by Thales Avionics (a Flight Management System) and in exhaustive tests show that the design and the prototype are reliable for industrial applications with strict timing requirements. Los sistemas empotrados y distribuidos de tiempo real son cada vez más importantes para la sociedad. Su demanda aumenta y cada vez más dependemos de los servicios que proporcionan. Los sistemas de alta integridad constituyen un subconjunto de gran importancia. Se caracterizan por que un fallo en su funcionamiento puede causar pérdida de vidas humanas, daños en el medio ambiente o cuantiosas pérdidas económicas. La necesidad de satisfacer requisitos temporales estrictos, hace más complejo su desarrollo. Mientras que los sistemas empotrados se sigan expandiendo en nuestra sociedad, es necesario garantizar un coste de desarrollo ajustado mediante el uso técnicas adecuadas en su diseño, mantenimiento y certificación. En concreto, se requiere una tecnología flexible e independiente del hardware. La evolución de las redes y paradigmas de comunicación, así como la necesidad de mayor potencia de cómputo y de tolerancia a fallos, ha motivado la interconexión de dispositivos electrónicos. Los mecanismos de comunicación permiten la transferencia de datos con alta velocidad de transmisión. En este contexto, el concepto de sistema distribuido ha emergido como sistemas donde sus componentes se ejecutan en varios nodos en paralelo y que interactúan entre ellos mediante redes de comunicaciones. Un concepto interesante son los sistemas de tiempo real neutrales respecto a la plataforma de ejecución. Se caracterizan por la falta de conocimiento de esta plataforma durante su diseño. Esta propiedad es relevante, por que conviene que se ejecuten en la mayor variedad de arquitecturas, tienen una vida media mayor de diez anos y el lugar ˜ donde se ejecutan puede variar. El lenguaje de programación Java es una buena base para el desarrollo de este tipo de sistemas. Por este motivo se ha creado RTSJ (Real-Time Specification for Java), que es una extensión del lenguaje para permitir el desarrollo de sistemas de tiempo real. Sin embargo, RTSJ no proporciona facilidades para el desarrollo de aplicaciones distribuidas de tiempo real. Es una limitación importante dado que la mayoría de los actuales y futuros sistemas serán distribuidos. El grupo DRTSJ (DistributedRTSJ) fue creado bajo el proceso de la comunidad de Java (JSR-50) con el fin de definir las abstracciones que aborden dicha limitación, pero en la actualidad aun no existe una especificacion formal. El objetivo de esta tesis es desarrollar un middleware de comunicaciones para el desarrollo de sistemas distribuidos de tiempo real en Java, basado en la integración entre el modelo de RMI (Remote Method Invocation) y el perfil HRTJ. Ha sido diseñado e implementado teniendo en cuenta los requisitos principales, como la predecibilidad y la confiabilidad del comportamiento temporal y el uso de recursos. El diseño parte de la definición de un modelo computacional el cual identifica entre otras cosas: el modelo de comunicaciones, los protocolos de red subyacentes más adecuados, el modelo de análisis, y un subconjunto de Java para sistemas de tiempo real crítico. En el diseño, las referencias remotas son el medio básico para construcción de aplicaciones distribuidas las cuales son asociadas a todos los parámetros no funcionales y los recursos necesarios para la ejecución de invocaciones remotas síncronas o asíncronas con atributos de tiempo real. El middleware propuesto separa la asignación de recursos de la propia ejecución definiendo dos fases y un mecanismo de hebras especifico que garantiza un comportamiento temporal adecuado. Además se ha incluido mecanismos para supervisar el comportamiento funcional y temporal. Se ha buscado independencia del protocolo de red definiendo una interfaz de red y módulos específicos. También se ha modificado el protocolo JRMP para incluir diferentes fases, parámetros no funcionales y optimizaciones de los tamaños de los mensajes. Aunque la serialización es una de las operaciones fundamentales para asegurar la adecuada transmisión de datos, las actuales implementaciones no son adecuadas para sistemas críticos y no hay alternativas. Este trabajo propone una serialización predecible que ha implicado el desarrollo de un nuevo compilador para la generación de código optimizado acorde al modelo computacional. La solución propuesta tiene la ventaja que en tiempo de compilación nos permite planificar las comunicaciones y ajustar el uso de memoria. Con el objetivo de validar el diseño e implementación se ha llevado a cabo un exigente proceso de validación con énfasis en: el comportamiento funcional, el uso de memoria, el uso del procesador (tiempo de respuesta de extremo a extremo y en cada uno de los bloques funcionales) y el uso de la red (consumo real conforme al estimado). Los buenos resultados obtenidos en una aplicación industrial desarrollada por Thales Avionics (un sistema de gestión de vuelo) y en las pruebas exhaustivas han demostrado que el diseño y el prototipo son fiables para aplicaciones industriales con estrictos requisitos temporales.

Distributed collaborative processing in wireless sensor networks with application to target localization and beamforming

Abstract The proliferation of wireless sensor networks and the variety of envisioned applications associated with them has motivated the development of distributed algorithms for collaborative processing over networked systems. One of the applications that has attracted the attention of the researchers is that of target localization where the nodes of the network try to estimate the position of an unknown target that lies within its coverage area. Particularly challenging is the problem of estimating the target’s position when we use received signal strength indicator (RSSI) due to the nonlinear relationship between the measured signal and the true position of the target. Many of the existing approaches suffer either from high computational complexity (e.g., particle filters) or lack of accuracy. Further, many of the proposed solutions are centralized which make their application to a sensor network questionable. Depending on the application at hand and, from a practical perspective it could be convenient to find a balance between localization accuracy and complexity. Into this direction we approach the maximum likelihood location estimation problem by solving a suboptimal (and more tractable) problem. One of the main advantages of the proposed scheme is that it allows for a decentralized implementation using distributed processing tools (e.g., consensus and convex optimization) and therefore, it is very suitable to be implemented in real sensor networks. If further accuracy is needed an additional refinement step could be performed around the found solution. Under the assumption of independent noise among the nodes such local search can be done in a fully distributed way using a distributed version of the Gauss-Newton method based on consensus. Regardless of the underlying application or function of the sensor network it is al¬ways necessary to have a mechanism for data reporting. While some approaches use a special kind of nodes (called sink nodes) for data harvesting and forwarding to the outside world, there are however some scenarios where such an approach is impractical or even impossible to deploy. Further, such sink nodes become a bottleneck in terms of traffic flow and power consumption. To overcome these issues instead of using sink nodes for data reporting one could use collaborative beamforming techniques to forward directly the generated data to a base station or gateway to the outside world. In a dis-tributed environment like a sensor network nodes cooperate in order to form a virtual antenna array that can exploit the benefits of multi-antenna communications. In col-laborative beamforming nodes synchronize their phases in order to add constructively at the receiver. Some of the inconveniences associated with collaborative beamforming techniques is that there is no control over the radiation pattern since it is treated as a random quantity. This may cause interference to other coexisting systems and fast bat-tery depletion at the nodes. Since energy-efficiency is a major design issue we consider the development of a distributed collaborative beamforming scheme that maximizes the network lifetime while meeting some quality of service (QoS) requirement at the re¬ceiver side. Using local information about battery status and channel conditions we find distributed algorithms that converge to the optimal centralized beamformer. While in the first part we consider only battery depletion due to communications beamforming, we extend the model to account for more realistic scenarios by the introduction of an additional random energy consumption. It is shown how the new problem generalizes the original one and under which conditions it is easily solvable. By formulating the problem under the energy-efficiency perspective the network’s lifetime is significantly improved. Resumen La proliferación de las redes inalámbricas de sensores junto con la gran variedad de posi¬bles aplicaciones relacionadas, han motivado el desarrollo de herramientas y algoritmos necesarios para el procesado cooperativo en sistemas distribuidos. Una de las aplicaciones que suscitado mayor interés entre la comunidad científica es la de localization, donde el conjunto de nodos de la red intenta estimar la posición de un blanco localizado dentro de su área de cobertura. El problema de la localization es especialmente desafiante cuando se usan niveles de energía de la seal recibida (RSSI por sus siglas en inglés) como medida para la localization. El principal inconveniente reside en el hecho que el nivel de señal recibida no sigue una relación lineal con la posición del blanco. Muchas de las soluciones actuales al problema de localization usando RSSI se basan en complejos esquemas centralizados como filtros de partículas, mientas que en otras se basan en esquemas mucho más simples pero con menor precisión. Además, en muchos casos las estrategias son centralizadas lo que resulta poco prácticos para su implementación en redes de sensores. Desde un punto de vista práctico y de implementation, es conveniente, para ciertos escenarios y aplicaciones, el desarrollo de alternativas que ofrezcan un compromiso entre complejidad y precisión. En esta línea, en lugar de abordar directamente el problema de la estimación de la posición del blanco bajo el criterio de máxima verosimilitud, proponemos usar una formulación subóptima del problema más manejable analíticamente y que ofrece la ventaja de permitir en¬contrar la solución al problema de localization de una forma totalmente distribuida, convirtiéndola así en una solución atractiva dentro del contexto de redes inalámbricas de sensores. Para ello, se usan herramientas de procesado distribuido como los algorit¬mos de consenso y de optimización convexa en sistemas distribuidos. Para aplicaciones donde se requiera de un mayor grado de precisión se propone una estrategia que con¬siste en la optimización local de la función de verosimilitud entorno a la estimación inicialmente obtenida. Esta optimización se puede realizar de forma descentralizada usando una versión basada en consenso del método de Gauss-Newton siempre y cuando asumamos independencia de los ruidos de medida en los diferentes nodos. Independientemente de la aplicación subyacente de la red de sensores, es necesario tener un mecanismo que permita recopilar los datos provenientes de la red de sensores. Una forma de hacerlo es mediante el uso de uno o varios nodos especiales, llamados nodos “sumidero”, (sink en inglés) que actúen como centros recolectores de información y que estarán equipados con hardware adicional que les permita la interacción con el exterior de la red. La principal desventaja de esta estrategia es que dichos nodos se convierten en cuellos de botella en cuanto a tráfico y capacidad de cálculo. Como alter¬nativa se pueden usar técnicas cooperativas de conformación de haz (beamforming en inglés) de manera que el conjunto de la red puede verse como un único sistema virtual de múltiples antenas y, por tanto, que exploten los beneficios que ofrecen las comu¬nicaciones con múltiples antenas. Para ello, los distintos nodos de la red sincronizan sus transmisiones de manera que se produce una interferencia constructiva en el recep¬tor. No obstante, las actuales técnicas se basan en resultados promedios y asintóticos, cuando el número de nodos es muy grande. Para una configuración específica se pierde el control sobre el diagrama de radiación causando posibles interferencias sobre sis¬temas coexistentes o gastando más potencia de la requerida. La eficiencia energética es una cuestión capital en las redes inalámbricas de sensores ya que los nodos están equipados con baterías. Es por tanto muy importante preservar la batería evitando cambios innecesarios y el consecuente aumento de costes. Bajo estas consideraciones, se propone un esquema de conformación de haz que maximice el tiempo de vida útil de la red, entendiendo como tal el máximo tiempo que la red puede estar operativa garantizando unos requisitos de calidad de servicio (QoS por sus siglas en inglés) que permitan una decodificación fiable de la señal recibida en la estación base. Se proponen además algoritmos distribuidos que convergen a la solución centralizada. Inicialmente se considera que la única causa de consumo energético se debe a las comunicaciones con la estación base. Este modelo de consumo energético es modificado para tener en cuenta otras formas de consumo de energía derivadas de procesos inherentes al funcionamiento de la red como la adquisición y procesado de datos, las comunicaciones locales entre nodos, etc. Dicho consumo adicional de energía se modela como una variable aleatoria en cada nodo. Se cambia por tanto, a un escenario probabilístico que generaliza el caso determinista y se proporcionan condiciones bajo las cuales el problema se puede resolver de forma eficiente. Se demuestra que el tiempo de vida de la red mejora de forma significativa usando el criterio propuesto de eficiencia energética.

Construcción de redes de pequeño mundo mediante selección sesgada.

En la actualidad las redes de Pequeño Mundo están presentes en muchas aplicaciones distribuidas, pudiéndose construir estas redes añadiendo, a un grafo base, enlaces de largo alcance tomados conforme a una determinada distribución de probabiblidad. Los sistemas distribuidos actuales utilizan soluciones ad hoc específicas para calcular los enlaces de largo alcance. En este artículo proponemos un nuevo algoritmo distribuido llamado Selección Sesgada (SS), que utilizando únicamente un servicio de muestreo uniforme (que puede estar implementado mediante un protocolo gossip), es capaz de seleccionar enlaces largos conforme a cualquier distribución de probabilidad. SS es un algoritmo iterativo que dispone de un único parámetro (r) para indicar el número de iteraciones que debe ejecutarse. Se ha probado que la muestra obtenida con el algoritmo SS converge a la distribución objetivo a medida que aumenta el valor de r. También se ha calculado la cota analítica del error relativo máximo, para un determinado valor de r. Aunque este artículo se propone para el algoritmo SS como una herramienta para tomar muestras de nodos en una red, puede emplearse en cualquier contexto en el que sea necesario realizar un muestreo conforme a una determinada distribución de probabilidad, necesitando para funcionar únicamente un servicio de muestreo uniforme. Se han construido redes de Pequeño Mundo, modelo Kleinberg, utilizando SS para escoger los enlaces (vecinos) de largo alcance en estructuras de tipo toro. Hemos observado que con un número reducido de iteraciones (1) SS tiene un comportamiento muy similar a la distribución armónica de Kleinberg y (2) el número medio de saltos, utilizando enrutamiento ávido, no es peor que en una red construida con la distribución de Leinberg. También se ha observado que antes de obtener la convergencia, el número medio de saltos es menor que en las redes construidas mediante la distribución armónica de Leinberg (14% mejor en un toro de 1000 x 1000).