Publicação: Uma Implementação Fiel do Algoritmo Generalized Paxos e uma CStruct para o Problema de Coordenação de Lease Distribuído
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
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.
Palavras-chave
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
Citação
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. DOI http://dx.doi.org/10.14393/ufu.di.2018.141