Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2017. / Made available in DSpace on 2017-11-21T03:19:13Z (GMT). No. of bitstreams: 1 348593.pdf: 2544042 bytes, checksum: 97b239bcf7b6ed2589435e05bfe4c249 (MD5) Previous issue date: 2017 / O armazenamento de dados em nuvens tem se tornado uma opção para permitir a geo-replicação. No contexto de aplicações críticas, é preciso garantir tolerância a faltas para que essas aplicações possam depender dos dados armazenados nas nuvens. Esta tese apresenta soluções para tornar mais simples e eficiente a operação de sistemas críticos que armazenam dados em múltiplos provedores de nuvem (Intercloud). Três contribuições integram esta tese. A primeira contribuição consiste em uma técnica denominada Antecipação de Pedidos (AdP) cujo objetivo é melhorar a eficiência de protocolos baseados em quóruns. Essa técnica é otimista e considera a latência dos provedores envolvidos na operação para paralelizar parcialmente fases de um protocolo. A aplicação da AdP no contexto desta tese resulta no RafeStore, um sistema confiável e eficiente de armazenamento de dados em múltiplas nuvens. O RafeStore considera uma categoria específica de dados multiversão, denominada Dado de Conteúdo Independente, cuja formação de novos valores não depende de valores anteriores. A avaliação do RafeStore usando provedores de nuvem comerciais demonstra que o mesmo requer menores latência e custo, quando comparado a outros sistemas baseados em quóruns bizantinos. A segunda contribuição desta tese refere-se à organização da execução de requisições, necessária quando múltiplos clientes atualizam simultaneamente um mesmo dado. Para tal fim, é proposto o sistema DORADO, que coordena metadados segundo a estratégia de replicação de máquinas de estado. O DORADO é projetado para funcionar no gerenciador de containers Kubernetes, visando o uso dessa emergente tecnologia de virtualização. A incorporação do DORADO ao Kubernetes por meio de integração torna a coordenação de metadados transparente sob a perspectiva do usuário. A avaliação de uma integração parcial demonstra a viabilidade dessa proposta. A contribuição final desta tese é o sistema denominado FITS, cuja função é orquestrar os sistemas RafeStore e DORADO. Dessa maneira, obtém-se um sistema de armazenamento de dados eficiente e tolerante a faltas que opera na Intercloud. / Abstract : Storing data in clouds has become an option in enabling geo-replication. In the context of critical systems, fault tolerance is required in order for the applications to be able to rely on the data stored in the cloud. This thesis presents solutions to simplify and make the operation of critical systems which store data in multiple cloud providers (Intercloud) more efficient. The contributions in this Thesis are threefold. The first contribution of this thesis consists in a technique to improve the efficiency of quorum-based protocols. We named it Requests Anticipation. This technique is optimistic and considers latency of providers to partially parallelize phases in a protocol. Applying request anticipation in the storage context results in RafeStore, a dependable and efficient system which stores data in multiple clouds. RafeStore considers a specific multiversion data type, named Data with Independent Content. With this type of data, new values are not necessarily related to previous ones. Our evaluation of RafeStore in commercial providers demonstrates that it requires lower latency and costs, when compared to other Byzantine quorum-based systems. The second contribution of this thesis refers to the organization of requests when multiple users simultaneously update the same data (i.e., race condition). To accomplish that, we propose DORADO: a system that manages metadata according to the strategy of state machine replication. DORADO was designed to work inside the container management system called Kubernetes, aiming at taking advantage of its emerging virtualization technology. Incorporating DORADO in Kubernetes via integration makes the metadata coordination transparent to the user. Our preliminary evaluation of the proposed approach demonstrates its viability. The third and final contribution of this thesis is FITS, a system that orchestrates RafeStore and DORADO. FITS enables the operation of an efficient and fault tolerant storage data system in the Intercloud.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2016. / Made available in DSpace on 2016-09-20T04:31:16Z (GMT). No. of bitstreams: 1 341439.pdf: 601566 bytes, checksum: 1cf4c567f598ff5b549d914b491f090c (MD5) Previous issue date: 2016 / Em sistemas de tempo real, inversão de prioridades é o problema em que há tarefas de alta prioridade críticas que devem ser executadas antes de tarefas de baixa prioridade, mas não conseguem. Em sistemas distribuídos tolerantes a faltas com replicação ativa, cada réplica deve, além de resolver o problema da inversão de prioridade, executar todas as tarefas na mesma ordem para manter a consistência. Os trabalhos existentes que resolvem o problema dependem de premissas fortes como o uso de serviços de consenso, o que faz com que o algoritmo execute com uma complexidade de mensagens trocadas quadrática ou cúbica. O trabalho proposto pretende modificar algoritmos de consenso para resolver o problema de inversão de prioridades sem depender de tais premissas fortes, com complexidade de mensagens linear.<br> / Abstract : In real-time systems, priority inversion is the problem in which there are higher priority tasks that must be executed before lower priority taks, but cannot. In fault tolerant distributed systems with active replication, each replica must, besides solving the problem of priority inversion, execute all requests at the same order to maintain consistency. Current works that solve the problem depend on strong assumptions like the use of consensus services, that causes the algorithm to execute with quadratic or cubic complexity of message transmission. The proposed work aims to adapt consensus algorithms in order to solve the priority inversion problem without depending on such strong assumptions, achieving linear message tranmission complexity.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2016. / Made available in DSpace on 2016-09-20T04:07:11Z (GMT). No. of bitstreams: 1 339452.pdf: 1160381 bytes, checksum: 722a35e532367f63e483a469497c4242 (MD5) Previous issue date: 2016 / Grafos são usados para modelar um grande número de problemas reais em áreas como aprendizado de máquina e mineração de dados. O crescimento das bases de dados destas áreas tem levado à criação de uma variedade de sistemas distribuídos para processamento de grafos muito grandes, dentre os quais se destaca o Pregel, da Google. Embora esses sistemas costumem ser tolerantes a faltas de parada, a literatura sugere que eles também estão suscetíveis a faltas arbitrárias acidentais. Neste trabalho é apresentado Greft, uma arquitetura para processamento distribuído de grafos de larga escala capaz de lidar com essas faltas, baseado no Graph Processing System (GPS), uma implementação de código aberto do Pregel. São apresentados também resultados experimentais do protótipo obtidos na Amazon Web Services (AWS), onde demonstra-se que este algoritmo usa o dobro de recursos do original, em vez de 3 ou 4 vezes, como é comum em modelos tolerantes a faltas Bizantinas. Com isso, seu custo torna-se aceitável para aplicações críticas que requerem esse nível de tolerância a faltas.<br> / Abstract : Graphs are used to model a large number of real problems in areas such as machine learning and data mining. The increasing dataset sizes has led to the creation of various distributed large scale graph processing systems, among which Google's Pregel stands out. Although these systems usually tolerate crash faults, literature suggests they are vulnerable to accidental arbitrary faults as well. In this dissertation we present the architecture, algorithms and a prototype of such system that can tolerate this kind of fault, based on Graph Processing System (GPS), an open source implementation of Pregel. Experimental results of the prototype in Amazon Web Services (AWS) are presented, showing that it uses twice the resources of the original implementation, instead of 3 or 4 times as usual in Byzantine fault-tolerant systems. This cost is acceptable for critical applications that require this level of fault tolerance.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-03T18:36:29Z No. of bitstreams: 1 REIS_Vinicius-2017.pdf: 1220818 bytes, checksum: 22e195232fbe4af89ae5ed34520da9b8 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-03T18:36:40Z (GMT) No. of bitstreams: 1 REIS_Vinicius-2017.pdf: 1220818 bytes, checksum: 22e195232fbe4af89ae5ed34520da9b8 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-03T18:36:49Z (GMT) No. of bitstreams: 1 REIS_Vinicius-2017.pdf: 1220818 bytes, checksum: 22e195232fbe4af89ae5ed34520da9b8 (MD5) / Made available in DSpace on 2017-10-03T18:36:56Z (GMT). No. of bitstreams: 1 REIS_Vinicius-2017.pdf: 1220818 bytes, checksum: 22e195232fbe4af89ae5ed34520da9b8 (MD5) Previous issue date: 2017-05-05 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A distributed system is a set of processes and links that is desgined to provide computing power and data persistency, even on the presence of failures. To encapsulate the abstraction of time and to determine which processes have currently failed, these distributed systems are based on unreliable failure detectors, which in its turn are used as a leader election service. Many works are dedicated to analyze the quality of service (QoS) of failure detectors, but a few of them has analyzed the QoS of a leader election algorithm. In this work, we present the NFD-L leader election algorithm, designed to work on crash-recovery distributed systems and to follow the QoS specification defined by Chen, Toueg e Aguilera (2002). We used NFD-L to elect Paxos coordinators for a replication framework and compared the observed QoS for NFD-L with the behavior of the framework native leader election algorithm that is not designed to explicitly meet any QoS requirement. / Um dos objetivos de um sistema distribuído é prover poder computacional e persistência de dados mesmo na presença de falhas de um subconjunto de enlaces e processos. Para determinar quais são os processos falhos deste sistema e abstrair o conceito de tempo, estes sistemas utilizam os serviços de um detector de falhas não confiável, encapsulado em um algoritmo de eleição de líder. Embora a literatura sobre a qualidade de serviço (QoS) oferecida por detectores de falhas seja abundante, ela é escassa quando se trata da QoS oferecida por algoritmos de eleição de líder. Neste trabalho propomos um algoritmo de eleição de líder para o modelo falha-e-recuperação denominado NFD-L, que segue as especificações de QoS originalmente apresentadas por Chen, Toueg e Aguilera (2002). Utilizamos NFD-L em uma aplicação para replicação, como mecanismo de eleição de coordenador para Paxos e apresentamos uma análise da QoS observada, comparando o seu comportamento com um algoritmo de eleição de líder que não foi projetado explicitamente para prover garantias de QoS.

O presente trabalho consiste na proposta de um novo protocolo de transporte para redes tolerantes a atrasos e desconexões (DTN - Delay Tolerant Network) chamado PTTA - Protocolo de Transporte Tolerante a Atrasos (em inglês - DTTP - Delay Tolerant Transport Protocol). Este protocolo tem o objetivo de oferecer uma confiabilidade estatística na entrega das informações em redes deste tipo. Para isso, serão utilizados Códigos Fontanais como técnica de correção de erros. Os resultados mostram as vantagens da utilização do PTTA. Este trabalho ainda propõe um mecanismo de controle da fonte adaptável para o PTTA a fim de limitar a quantidade de dados gerados pela origem (fonte). O esquema proposto almeja aumentar a diversidade das informações codificadas sem o aumento da carga na rede. Para atingir este objetivo o intervalo de geração e o TTL (Time To Live - Tempo de vida) das mensagens serão manipulados com base em algumas métricas da rede. A fim de validar a eficiência do mecanismo proposto, diferentes cenários foram testados utilizando os principais protocolos de roteamento para DTNs. Os resultados de desempenho foram obtidos levando em consideração o tamanho do buffer, o TTL das mensagens e a quantidade de informação redundante gerada na rede. Os resultados de simulações obtidos através do simulador ONE mostram que nos cenários avaliados, o PTTA alcança um aumento na taxa de entrega das informações em um menor tempo, quando comparado com outro protocolo de transporte sem confirmação, permitindo assim um ganho de desempenho na rede. / The present work consists in the proposal of a new transport protocol for delay tolerant networks and disconnections (DTN - Delay Tolerant Network) called DTTP - Delay Tolerant Transport Protocol (in portuguese – PTTA - Protocolo de Transporte Tolerante a Atrasos). This protocol aims to provide a statistical reliability in DTNs' information delivery. For this, we use fountain codes as error correction technique. The results show the advantages of using DTTP. This work also proposes an adaptive control mechanism for the DTTP source to limit the amount of generated data. The proposed scheme aims at increasing the diversity of encoded information without increasing the load on the network. To achieve this goal the messages generation interval and TTL (Time To Live) will be handled based on some network metrics. In order to validate the efficiency of the proposed mechanism, different scenarios will be tested using the main routing protocols for DTNs. The performance results were obtained taking into account the buffer size, messages TTL and the amount of redundant information generated on the network. The simulation results, obtained through The ONE simulator, show that in the evaluated scenarios PTTA achieves an increase in the information delivery rate in a shorter time compared to other transport protocol for confirmation, thus allowing a gain in the network performance.

Esta tese apresenta um novo protocolo de roteamento voltado para as Redes Tolerantes a Atrasos que exibem comportamentos complexos e dinâmicos. O protocolo proposto chama-se Cultural GrAnt (do inglês Cultural Greedy Ant) uma vez que este utiliza um sistema híbrido composto por um Algoritmo Cultural (AC) e uma versão gulosa da meta-heurística de Otimização por Colônia de Formigas (ACO). No Cultural GrAnt, o ACO representa o espaço populacional de um AC e utiliza uma regra de transição gulosa de modo a intensificar bons caminhos já encontrados ou explorar novos caminhos através da seleção, dentre um conjunto de candidatos, dos nós encaminhadores de mensagens mais promissores. A principal motivação para o uso do ACO é tirar proveito da sua busca baseada em população de indivíduos e da adaptação da sua estrutura de aprendizado. O AC obtém informações durante o processo evolucionário e as utiliza para guiar a população e, então, acelerar o aprendizado enquanto provê soluções mais eficientes. Considerando informações de funções heurísticas, concentração de feromônio e conhecimentos armazenados no espaço de crenças do AC, o protocolo Cultural GrAnt inclui três módulos: roteamento; escalonamento; e gerenciamento de buffer. Esse é o primeiro protocolo de roteamento que emprega ACO e AC de modo a: inferir os melhores encaminhadores de mensagens através de informações oportunistas sobre a conectividade social entre os nós; determinar os melhores caminhos que uma mensagem deve seguir para eventualmente alcançar o seu destino final, enquanto limita o número de replicações e descartes de mensagens na rede; determinar a ordem de escalonamento das mensagens; e gerenciar o espaço de armazenamento do buffer dos nós. O protocolo Cultural GrAnt é comparado com os protocolos Epidêmico e PROPHET em dois cenários de mobilidade distintos: um modelo de movimento baseado em atividades, onde simula-se o dia-a-dia de pessoas em suas atividades de trabalho, lazer e descanso; e um modelo de movimento baseado em comunidades de pessoas. Os resultados de simulações obtidos através do simulador ONE mostram que em ambos os cenários, o protocolo Cultural GrAnt alcança uma taxa mais alta de entrega de mensagens, uma replicação menor de mensagens e um número menor de mensagens descartadas se comparado com os protocolos Epidêmico e PROPHET. / This work presents a new routing protocol for complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called Cultural GrAnt (Greedy Ant), as it uses a hybrid system composed of a Cultural Algorithm and a greedy version of the Ant Colony Optimization (ACO) metaheuristic. In Cultural GrAnt, ACO represents the population space of the cultural algorithm and uses a greedy transition rule to either exploit previously found good paths or explore new paths by selecting, among a set of candidates, the most promising message forwarders. The main motivation for using ACO is to take advantage of its population-based search and adaptive learning framework. Conversely, CA gathers information during the evolutionary process and uses it to guide the population and thus accelerate learning while providing more efficient solutions. Considering information from heuristic functions, pheromone concentration, and knowledge stored in the CA belief space, the Cultural GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first routing protocol that employs both ACO and CA to infer the best message forwarders using opportunistic information about social connectivity between nodes, determine the best paths a message must follow to eventually reach its destination while limiting message replications and droppings, and perform message transmission scheduling and buffer space management. Cultural GrAnt is compared to the Epidemic and PROPHET protocols in two different mobility scenarios: an activity-based movement model, which simulates the daily lives of people in their work, leisure and rest activities; and a community-based movement model. Simulation results obtained by the ONE simulator show that, in both scenarios, Cultural GrAnt achieves a higher delivery ratio, lower message replication, and fewer dropped messages than Epidemic and PROPHET.

O presente trabalho consiste na proposta de um novo protocolo de transporte para redes tolerantes a atrasos e desconexões (DTN - Delay Tolerant Network) chamado PTTA - Protocolo de Transporte Tolerante a Atrasos (em inglês - DTTP - Delay Tolerant Transport Protocol). Este protocolo tem o objetivo de oferecer uma confiabilidade estatística na entrega das informações em redes deste tipo. Para isso, serão utilizados Códigos Fontanais como técnica de correção de erros. Os resultados mostram as vantagens da utilização do PTTA. Este trabalho ainda propõe um mecanismo de controle da fonte adaptável para o PTTA a fim de limitar a quantidade de dados gerados pela origem (fonte). O esquema proposto almeja aumentar a diversidade das informações codificadas sem o aumento da carga na rede. Para atingir este objetivo o intervalo de geração e o TTL (Time To Live - Tempo de vida) das mensagens serão manipulados com base em algumas métricas da rede. A fim de validar a eficiência do mecanismo proposto, diferentes cenários foram testados utilizando os principais protocolos de roteamento para DTNs. Os resultados de desempenho foram obtidos levando em consideração o tamanho do buffer, o TTL das mensagens e a quantidade de informação redundante gerada na rede. Os resultados de simulações obtidos através do simulador ONE mostram que nos cenários avaliados, o PTTA alcança um aumento na taxa de entrega das informações em um menor tempo, quando comparado com outro protocolo de transporte sem confirmação, permitindo assim um ganho de desempenho na rede. / The present work consists in the proposal of a new transport protocol for delay tolerant networks and disconnections (DTN - Delay Tolerant Network) called DTTP - Delay Tolerant Transport Protocol (in portuguese – PTTA - Protocolo de Transporte Tolerante a Atrasos). This protocol aims to provide a statistical reliability in DTNs' information delivery. For this, we use fountain codes as error correction technique. The results show the advantages of using DTTP. This work also proposes an adaptive control mechanism for the DTTP source to limit the amount of generated data. The proposed scheme aims at increasing the diversity of encoded information without increasing the load on the network. To achieve this goal the messages generation interval and TTL (Time To Live) will be handled based on some network metrics. In order to validate the efficiency of the proposed mechanism, different scenarios will be tested using the main routing protocols for DTNs. The performance results were obtained taking into account the buffer size, messages TTL and the amount of redundant information generated on the network. The simulation results, obtained through The ONE simulator, show that in the evaluated scenarios PTTA achieves an increase in the information delivery rate in a shorter time compared to other transport protocol for confirmation, thus allowing a gain in the network performance.

Esta tese apresenta um novo protocolo de roteamento voltado para as Redes Tolerantes a Atrasos que exibem comportamentos complexos e dinâmicos. O protocolo proposto chama-se Cultural GrAnt (do inglês Cultural Greedy Ant) uma vez que este utiliza um sistema híbrido composto por um Algoritmo Cultural (AC) e uma versão gulosa da meta-heurística de Otimização por Colônia de Formigas (ACO). No Cultural GrAnt, o ACO representa o espaço populacional de um AC e utiliza uma regra de transição gulosa de modo a intensificar bons caminhos já encontrados ou explorar novos caminhos através da seleção, dentre um conjunto de candidatos, dos nós encaminhadores de mensagens mais promissores. A principal motivação para o uso do ACO é tirar proveito da sua busca baseada em população de indivíduos e da adaptação da sua estrutura de aprendizado. O AC obtém informações durante o processo evolucionário e as utiliza para guiar a população e, então, acelerar o aprendizado enquanto provê soluções mais eficientes. Considerando informações de funções heurísticas, concentração de feromônio e conhecimentos armazenados no espaço de crenças do AC, o protocolo Cultural GrAnt inclui três módulos: roteamento; escalonamento; e gerenciamento de buffer. Esse é o primeiro protocolo de roteamento que emprega ACO e AC de modo a: inferir os melhores encaminhadores de mensagens através de informações oportunistas sobre a conectividade social entre os nós; determinar os melhores caminhos que uma mensagem deve seguir para eventualmente alcançar o seu destino final, enquanto limita o número de replicações e descartes de mensagens na rede; determinar a ordem de escalonamento das mensagens; e gerenciar o espaço de armazenamento do buffer dos nós. O protocolo Cultural GrAnt é comparado com os protocolos Epidêmico e PROPHET em dois cenários de mobilidade distintos: um modelo de movimento baseado em atividades, onde simula-se o dia-a-dia de pessoas em suas atividades de trabalho, lazer e descanso; e um modelo de movimento baseado em comunidades de pessoas. Os resultados de simulações obtidos através do simulador ONE mostram que em ambos os cenários, o protocolo Cultural GrAnt alcança uma taxa mais alta de entrega de mensagens, uma replicação menor de mensagens e um número menor de mensagens descartadas se comparado com os protocolos Epidêmico e PROPHET. / This work presents a new routing protocol for complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called Cultural GrAnt (Greedy Ant), as it uses a hybrid system composed of a Cultural Algorithm and a greedy version of the Ant Colony Optimization (ACO) metaheuristic. In Cultural GrAnt, ACO represents the population space of the cultural algorithm and uses a greedy transition rule to either exploit previously found good paths or explore new paths by selecting, among a set of candidates, the most promising message forwarders. The main motivation for using ACO is to take advantage of its population-based search and adaptive learning framework. Conversely, CA gathers information during the evolutionary process and uses it to guide the population and thus accelerate learning while providing more efficient solutions. Considering information from heuristic functions, pheromone concentration, and knowledge stored in the CA belief space, the Cultural GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first routing protocol that employs both ACO and CA to infer the best message forwarders using opportunistic information about social connectivity between nodes, determine the best paths a message must follow to eventually reach its destination while limiting message replications and droppings, and perform message transmission scheduling and buffer space management. Cultural GrAnt is compared to the Epidemic and PROPHET protocols in two different mobility scenarios: an activity-based movement model, which simulates the daily lives of people in their work, leisure and rest activities; and a community-based movement model. Simulation results obtained by the ONE simulator show that, in both scenarios, Cultural GrAnt achieves a higher delivery ratio, lower message replication, and fewer dropped messages than Epidemic and PROPHET.