Dissertação

{en_GB=Generalized Paxos made Byzantine, Visigoth and Less Complex} {} EVALUATED

{pt=Um dos membros mais recentes da família de protocolos Paxos é o protocolo Generalized Paxos. Esta variante tem a característica de se separar da especificação original de consenso, o que lhe permite ter uma condição de consistência mais fraca onde diferentes processos podem ter noções diferentes da sequência de comandos que está a ser concordada. No entanto, tal como o Paxos original, o protocolo Generalized Paxos não tem uma implementação simples. Para além disso, com a recente adoção prática de protocolos de tolerância a faltas Bizantinas, é relevante entender como é que o Generalized Paxos pode ser implementado no modelo Bizantino. O mesmo pode ser dito relativamente ao modelo Visigoth que tem como alvos ambientes semelhantes a datacenters ao permitir assunções de faltas e sincronia parametrizáveis. Esta dissertação faz várias contribuições. Em primeiro lugar, fornecemos uma descrição do protocolo Generalized Paxos mais fácil de entender, baseada numa especificação de consenso simplificada, juntamente com uma especificação em pseudocódigo que pode ser prontamente implementada. Em segundo lugar, estendemos o protocolo para o modelo de faltas Bizantino, fornecendo também uma descrição em pseudocódigo para facilitar o seu mapeamento numa linguagem de programação. Esta contribuição é suplementada com provas de correção e uma discussão de extensões e otimizações relevantes. Em terceiro lugar, expandimos esta implementação para o modelo de faltas Visigoth, fornecendo também uma descrição acessível em pseudocódigo e provas de correção. , en=One of the most recent members of the Paxos family of protocols is Generalized Paxos. This variant of Paxos has the characteristic that it departs from the original specification of consensus, allowing for a weaker safety condition where different processes can have different views of a sequence being agreed upon. However, much like its original Paxos counterpart, Generalized Paxos does not have a simple implementation. Furthermore, with the recent practical adoption of Byzantine fault tolerant protocols, it is timely and important to understand how Generalized Paxos can be implemented in the Byzantine model. The same point can be made with respect to the Visigoth model which targets datacenter-like environments by allowing parameterizable fault and synchrony assumptions. This dissertation makes several contributions. First, we provide a description of Generalized Paxos that is easier to understand, based on a simpler specification of consensus, along with a pseudocode specification that can be readily implemented. Second, we extend the protocol to the Byzantine fault model, providing also a pseudocode description to ease its mapping into a code implementation. This contribution is supplemented with correctness proofs and a discussion of relevant extensions and optimizations. Third, we extend this implementation to the Visigoth fault model, providing with it an accessible pseudocode description and correctness proofs. }
{pt=Paxos, Consenso, Tolerância a faltas, Modelo de Faltas Bizantinas, en=Paxos, Consensus, Fault Tolerance, Byzantine Fault Model}

Novembro 2, 2017, 17:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Rodrigo Seromenho Miragaia Rodrigues

Departamento de Engenharia Informática (DEI)

Professor Catedrático