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. Disponível em: 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 SizeFormat 
ImplementacaoAvaliacaoProtocolo.pdfDISSERTAÇÂO18.71 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.