Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/22447
Document type: | Dissertação |
Access type: | Acesso Aberto |
Title: | Implementação e Avaliação do Protocolo de Difusão Atômica Rápida a Despeito de Colisões |
Alternate title (s): | Implementation and evaluation of the Collision-fast Atomic Broadcast protocol |
Author: | Saramago, Rodrigo Queiroz |
First Advisor: | Camargos, Lásaro Jonas |
First member of the Committee: | Alchieri, Eduardo Adilio Pelinson |
Second member of the Committee: | Faina, Luís Fernando |
Third member of the Committee: | Vieira, Gustavo Maciel Dias |
Summary: | Replicação de Máquinas de Estados, uma técnica comum para se alcançar tolerância a falhas, pode ser implementada por meio de primitivas de Difusão Atômica (Atomic Broadcast). Difusão Atômica, por sua vez, é comumente implementada via algoritmos de Consensus: com infinitas instâncias de Consensus, totalmente ordenadas, decide-se por uma sequência de comandos a serem executados na máquina de estados replicada. Esta abordagem tem a desvantagem de forçar as propostas não decididas (comandos não entregues) a serem repropostas em novas instâncias, atrasando sua execução. Algoritmos que evitam tais problemas são denominados collision-fast e apresentam uma latência ótima de dois passos de comunicação. Os existentes, contudo, requerem um certo grau de sincronismo (Clock-RSM), ou não tratam falhas de forma eficiente (Mencius) ou ainda não foram avaliados experimentalmente (CFABCAST). Este trabalho objetiva primariamente a implementação do algoritmo Collision-fast Atomic Broadcast (CFABCAST), bem como uma avaliação de desempenho em relação ao modelo clássico de replicação de máquinas de estado baseado no Paxos, e a outro trabalho denominado Multi Ring Paxos. Além disso, este trabalho tem como objetivos adicionais, melhorar a eficiência do protocolo em sistemas que permitam execução especulativa e torná-lo resiliente a falhas bizantinas. Por fim, conjecturamos ser impossível existir um protocolo Collision-fast que tolere falhas bizantinas. |
Abstract: | State Machine Replication, is a common technique for achieving fault tolerance that can be implemented by Atomic Broadcast primitives. Atomic Broadcast is usually implemented by solving infinitely many instances of the well-known consensus problem. This approach has the disadvantage of forcing the concurrent broadcast of messages that have not yet been decided, causing them to be re-proposed in new instances, therefore delaying execution. Collision-fast algorithms, which deliver many messages within two message steps in good runs, exist, but either make assumptions that may be too restrictive; require a certain degree of clock synchronization among nodes; do not deal efficiently with failures or have not been experimentally evaluated. In this work we propose an architecture to implement the Collision-fast Atomic Broadcast algoritm as part of a distributed service, exploring the parallelism in today’s machines, and also evaluating the performance of this protocol in a variety of scenarios, comparing it with other two protocols (Paxos and Multi-Ring Paxos). Moreover, this work aims at improving the protocol to allow speculative execution of delivered commands and make it resilient to Byzantine failures. Finally, we conjecture the impossibility of Byzantine failure tolerant Collision-fast protocols. |
Keywords: | Computação Computing Sistemas Distribuídos Dystributed Systems Algoritmos Algorithms Consenso Distribuído Distributed Consensus Difusão Atômica Atomic Broadcast Paxos Multi Ring Paxos M-consensus Collision-fast Replicação de Máquinas de Estado State Machine Replication Consenso Bizantino Byzantine Consensus Sistemas distribuidos - Protocolos |
Area (s) of CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
Language: | por |
Country: | Brasil |
Publisher: | Universidade Federal de Uberlândia |
Program: | Programa de Pós-graduação em Ciência da Computação |
Quote: | SARAMAGO, Rodrigo Queiroz. Implementação e Avaliação do Protocolo de Difusão Atômica Rápida a Despeito de Colisões. 2016. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2018. DOI http://dx.doi.org/10.14393/ufu.di.2018.1147. |
Document identifier: | http://dx.doi.org/10.14393/ufu.di.2018.1147 |
URI: | https://repositorio.ufu.br/handle/123456789/22447 |
Date of defense: | 8-Sep-2016 |
Appears in Collections: | DISSERTAÇÃO - Ciência da Computação |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ImplementacaoAvaliacaoProtocolo.pdf | DISSERTAÇÂO | 18.71 MB | Adobe PDF | ![]() View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.