Orientador: Luiz Eduardo Buzato

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Protocolos de Difusão Totalmente Ordenada (DTO) constituem o núcleo de diversas soluções que dão suporte ao desenvolvimento de aplicações distribuídas tolerantes a falhas. O longo período no qual este problema vem sendo objeto de pesquisa e a quantidade de algoritmos que foram para ele...

Resumo: Protocolos de Difusão Totalmente Ordenada (DTO) constituem o núcleo de diversas soluções que dão suporte ao desenvolvimento de aplicações distribuídas tolerantes a falhas. O longo período no qual este problema vem sendo objeto de pesquisa e a quantidade de algoritmos que foram para ele propostos atestam, não só a sua importância, mas também a dificuldade de se obter soluções eficientes para DTO. Este trabalho apresenta um novo algoritmo de DTO, que explora a sincronia e a confiabilidade inerentes ao ambiente dos aglomerados ou clusters de alto desempenho para construir uma solução bastante simples de Difusão Totalmente Ordenada, cujo desempenho experimental mostrou-se comparável ao obtido por soluções de DTO projetadas para modelos assíncronos de computação. O protocolo proposto destina-se ao modelo assíncrono temporizado de computação, aumentado com um mecanismo simples, baseado na difusão de pulsos, para sincronizá-la a execução dos processos. A hipótese que sustenta este mecanismo de sincronização é que os aglomerados modernos, dado que se controle a carga a eles aplicada, podem executar por períodos razoavelmente longos sem que ocorram falhas de processos e apresentando um comportamento bastante similar ao de sistemas síncronos. Dada esta hipótese, os processos que realizam Difusão Totalmente Ordenada tornam-se capazes de construir visões globais da computação distribuída, e a construção de visões globais, por sua vez, torna trivial a resolução de Difusão Totalmente Ordenada. O protocolo proposto tolera uma quantidade ilimitada de falhas de desempenho, que previnem o progresso da solução de DTO, mas que não levam à violação de suas propriedades de segurança, que são asseguradas na presença de assincronia e de falhas de processos. O protocolo foi implementado em Java e o seu desempenho foi avaliado em um aglomerado com máquinas interconectadas via Ethernet. A comparação dos resultados obtidos com os resultados de desempenho publicados para as principais soluções de DTO existentes nos permite afirmar que nossa solução representa um interessante compromisso entre desempenho experimental e simplicidade de projeto e implementação de soluções de Difusão Totalmente Ordenada. Além dos resultados de desempenho, esta pesquisa também revela que ainda há espaço para a exploração prática da interação entre sincronia e assincronia na engenharia de protocolos distribuídos

Abstract: Total order broadcast algorithms are at the core of several toolkits for the construction of fault-tolerant applications. The importance and the difficulty of finding efficient total order broadcast (TOB) algorithms is attested by the long period that such algorithms have been the object...

Abstract: Total order broadcast algorithms are at the core of several toolkits for the construction of fault-tolerant applications. The importance and the difficulty of finding efficient total order broadcast (TOB) algorithms is attested by the long period that such algorithms have been the object of intense research and by the large number of algorithms already proposed. This work presents a new algorithm for total order broadcast that takes advantage of the inherent reliability and timeliness of high performance clusters in its design. Experimental results show that the performance of this very simple TOB is on a par with the performance of TOBs designed for asynchronous computing models. The proposed protocol has been designed for the timed asynchronous computing model, enhanced with a simple pulse-based mechanism that is used to synchronize the processes' execution. The assumption behind the pulse-based synchronization is that modern clusters, given some workload conditioning, can maintain reasonably long failure-free execution periods in which they behave very much as synchronous system. This assumption allows the processes that engage in total order broadcasts to build a global view of their joint computation and this global view, in its turn, allows them to solve total order broadcast in a straightforward way. The protocol tolerates an unbounded number of timing failures, that can prevent its progress but have no impact on its safety, it is also safe in the in the presence of asynchrony, and processes failures. The protocol has been implemented in Java and tested on an Ethernet-based cluster. A comparison of the results obtained in the experiments with results published for other well-known TOBs allow us to conclude that our solution represents an interesting trade-o_ between performance and simplicity of design and implementation for total order broadcasts protocols. Beyond performance, this research seems to indicate that there is still room for the practical exploration of the interplay between synchronicity and asynchronicity in the engineering of distributed protocols