Investigando a implementação do consenso escalável sobre o VCUBE

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorDuarte Junior, Elias Procópio, 1966--
Autor(es): dc.contributorCamargo, Edson Tavares de-
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorTerra, Acácia dos Campos, 1996--
Data de aceite: dc.date.accessioned2020-09-24T17:25:29Z-
Data de disponibilização: dc.date.available2020-09-24T17:25:29Z-
Data de envio: dc.date.issued2020-08-04-
Data de envio: dc.date.issued2020-08-04-
Data de envio: dc.date.issued2019-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/67885-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/67885-
Descrição: dc.descriptionOrientador: Prof. Dr. Elias Procópio Duarte Jr.-
Descrição: dc.descriptionCoorientador: Prof. Dr. Edson Tavares de Camargo.-
Descrição: dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 17/04/2020-
Descrição: dc.descriptionInclui referências: p. 41-42-
Descrição: dc.descriptionÁrea de concentração: Ciência da Computação-
Descrição: dc.descriptionResumo: Um dos algoritmos essenciais na construção de sistemas distribuídos é o consenso, que garante que todos os processos corretos do sistema decidem por um mesmo valor dentre valores que foram propostos. O Paxos é um dos mais importantes algoritmos de consenso existentes. O Paxos tolera falhas por parada, garantindo a propriedade da segurança (safety) e, sob condições de assincronia fraca, garante o progresso (liveness). O Paxos foi proposto originalmente para a replicação máquina de estado. Variações do algoritmo, com destaque para o Ring Paxos, foram propostas com o intuito de melhorar o desempenho do sistema. O Ring Paxos executa o Paxos dispondo os processos em um anel lógico direcional. Neste trabalho é proposto um algoritmo de consenso escalável que implementa uma instância do Paxos. No algoritmo os processos acceptors são organizados na topologia virtual para sistemas distribuídos conhecida como VCube. O VCube organiza os processos em um hipercubo quando todos estão sem-falha, sendo um algoritmo que apresenta diversas propriedades logarítmicas mesmo quando há processos falhos. No algoritmo proposto, os acceptors são agrupados em clusters, e o coordenador executa o Paxos utilizando uma difusão de mensagens de melhor esforço sobre o VCube. Inicialmente o algoritmo tenta alcançar a maioria apenas no maior cluster. Caso haja processos falhos o algoritmo continua nos demais clusters até que obtenha uma maioria de acceptors. Conforme um acceptor encaminha a mensagem recebida para o próximo acceptor no cluster, concatena junto à mensagem a sua resposta para o coordenador. A mensagem percorre o ramo da árvore gerada pelo VCube e, sempre que um acceptor for folha, envia uma mensagem de resposta para o coordenador contendo as respostas concatenadas de todos os acceptors daquele ramo. Desta forma o coordenador sabe quando atingiu uma maioria entre os N acceptors. O algoritmo foi implementado através de simulação e foram obtidos resultados positivos para a quantidade de mensagens trocadas durante a execução do consenso, quando em comparação com uma versão do Paxos em anel inspirada no Ring Paxos. Nesta dissertação é apresentada uma especificação, implementação e os resultados obtidos através de simulação. Palavras-chave: VCube. Sistema Distribuído. Consenso. Paxos. Tolerância a Falhas.-
Descrição: dc.descriptionAbstract: Consensus is one of the most important building blocks for building fault-tolerant distributed systems. The execution of consensus ensures that all the correct processes in the system decide the same value among a set of values initially proposed. Paxos is one of the most important consensus algorithms. Paxos tolerates crash faults, guarantees safety always, and liveness under weak synchrony assumptions. Paxos was originally proposed for state machine replication. Variations of the algorithm, in particular Ring Paxos, have been proposed in order to improve the performance of the system. Ring Paxos executes Paxos by organizing the processes on a directional logical ring. This work proposes a scalable consensus algorithm that implements an instance of Paxos. In the algorithm, acceptors are organized in a virtual topology for distributed systems known as VCube. The VCube is a hypercube when every process is correct, and presents several logarithmic properties even when processes fail. In the proposed algorithm, the acceptors are grouped in clusters, and the coordinator runs Paxos using a best effort broadcast algorithm that sends messages across the VCube. Initially the algorithm tries to reach a majority only in the largest cluster. In case there are faulty processes, the algorithm continues in the other clusters until it reaches a majority of acceptors. As an acceptor forwards the received message to the next acceptor in the cluster, it concatenates its response in the message that is sent up to the coordinator. The message travels through branches of the tree generated on the VCube and, whenever an acceptor is a leaf, it sends a reply message to the coordinator containing the concatenated responses of all acceptors of that branch. In this way as the coordinator receives the message it knows whether a majority among the N acceptors has replied. The algorithm was implemented through simulation and positive results were obtained for the amount of messages exchanged during the execution of the consensus, when compared to an equivalent Paxos version inspired on Ring Paxos. In this dissertation we present a specification of the algorithm, as well as an implementation and results obtained through simulation. Keywords: VCube. Distributed System. Consensus. Paxos. Fault Tolerance.-
Formato: dc.format42 p. : il. (algumas color.).-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Palavras-chave: dc.subjectAlgorítmos de computador-
Palavras-chave: dc.subjectSistemas operacionais distribuidos (Computadores)-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleInvestigando a implementação do consenso escalável sobre o VCUBE-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.