Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/22458
Document type: Dissertação
Access type: Acesso Aberto
Title: Uma Implementação Fiel do Algoritmo Generalized Paxos e uma CStruct para o Problema de Coordenação de Lease Distribuído
Alternate title (s): A Faithful Generalized Paxos Implementation and a Novel CStruct for Distributed Lease Coordination
Author: Rezende, Tuanir França
First Advisor: Camargos, Lasaro Jonas
First member of the Committee: Faina, Luis Fernando
Second member of the Committee: Vieira, Gustavo Maciel Dias
Summary: Replicação de Máquina de Estados é uma abordagem amplamente aceita para se con- struir um sistema distribuído tolerante a falhas. Nesta técnica, as réplicas entram em acordo a respeito da sequência de comandos que irão executar, o que consiste no prob- lema fundamental do consenso distribuído. Devido a deĄnição básica do problema do consenso, as soluções existentes mais conhecidas para o mesmo não relevam o fato de que não é necessária a deĄnição de uma ordem total para a sequência de comandos que as réplicas executam. O algoritmo chamado: Generalized Paxos resolve uma versão mais genérica e versátil do problema do consenso, que exige apenas que as réplicas entrem em acordo a respeito de uma ordem parcial da sequência de comandos. Além de ser uma das versões mais otimizadas para se implementar replicação de máquina de estados, o algoritmo Generalized Paxos é capaz de resolver diferentes tipos de problema de acordo. Apesar disso, o potencial do algoritmo não é totalmente explorado devido a sua alta com- plexidade e a baixa quantidade de estudos e implementações do mesmo. Este trabalho tem o intuito de diminuir as lacunas existentes entre a teoria e prática no Generalized Paxos, através da implementação do algoritmo e otimizações que podem ser aplicadas à mesma. Além disso, atestando em favor do uso de Generalized Paxos em problemas do mundo real, este trabalho também fornece uma nova formalização que permite que o algoritmo solucione uma variação do problema de coordenação de leases em ambientes distribuídos.
Abstract: State Machine Replication is a broadly accepted approach to build a fault-tolerant distributed system. In this technique, replicas agree on a sequence of commands that they will execute. This consists in the fundamental Consensus problem in distributed systems. The classical Consensus problem and its solutions do not leverage the fact that the sequence of commands executed by the replicas does not need to follow a total order. The algorithm entitled Generalized Paxos solves a more generic and versatile version of the Consensus problem by requiring that the replicas agree on a partially ordered sequence of commands. As well as being one of the most optimized solutions to implement state machine replication, Generalized Paxos is also capable of solving diferent agreement problems. However, due to its high complexity and the small amount of research attesting its beneĄts, the algorithmŠs potential is not fully explored. This work aims at diminishing the gap between theory and practice regarding Generalized Paxos, through an implementation of the algorithm and optimizations that can be applied to it. Furthermore, to advocate the use of Generalized Paxos in real-world problems, this work provides a new construct that allows the algorithm to solve a variation of the lease coordination problem in distributed systems.
Keywords: Consenso Distribuído
Consenso Generalizado
Paxos
Generalized Paxos
Sistemas Distribuídos
Replicação de máquinas de estado
Coordenação de leases
Distributed Consensus
Generalized Consensus
Distributed Systems
State Machine Replication
Lease Coordination
Computação
Algoritmos
Análise de sistemas (Computação)
Otimização estrutural
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Language: eng
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: REZENDE, Tuanir França. Uma implementação fiel do algoritmo Generalized Paxos e uma CStruct para o problema de coordenação de Lease Distribuído. 2017. 87f. 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.141
Document identifier: http://dx.doi.org/10.14393/ufu.di.2018.141
URI: https://repositorio.ufu.br/handle/123456789/22458
Date of defense: 5-Jan-2017
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
UmaImplementaçãoFiel.pdfDissertação6.49 MBAdobe PDFThumbnail
View/Open


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