Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/332151
Type: TESE DIGITAL
Degree Level: Doutorado
Title: The role of synchrony on the performance of Paxos : O papel da sincronia no desempenho de Paxos
Title Alternative: O papel da sincronia no desempenho de Paxos
Author: Cason, Daniel, 1987-
Advisor: Buzato, Luiz Eduardo, 1961-
Abstract: Resumo: Algoritmos de consenso e de difusão totalmente ordenada são centrais para a implementação de aplicações distribuídas tolerantes a falhas. Paxos é um algoritmo assíncrono de consenso comumente empregado para a implementação de difusão totalmente ordenada. De forma breve, Paxos proporciona que mensagens enviadas a um conjunto de processos sejam a eles entregues em uma mesma ordem total. Uma funcionalidade que é simples de se obter sob condições normais de operação de um sistema distribuído, mas que se torna reconhecidamente complicada quando se observa uma mescla de assincronia e falhas. O projeto assíncrono de Paxos visa assegurar um comportamento consistente sob condições particularmente adversas de operação: a robustez é o seu maior atributo. Mas quando se trata da operação regular do sistema, sem falhas e predominantemente síncrona, Paxos peca por não oferecer um desempenho compatível com os recursos disponíveis. A busca por formas de se melhorar o desempenho de Paxos ganha importância quando o algoritmo passa a compor o núcleo de várias soluções de replicação. De fato, múltiplas variações de Paxos destinadas a obter difusão totalmente ordenada de alto desempenho foram propostas em paralelo ao nosso Doutorado. Elas abordam limitações do algoritmo original e sugerem alterações, que vão desde a reorganização da topologia até otimizações no uso da rede pelos processos. A nossa abordagem difere das existentes, ou paralelas, por envolver a adoção explícita de pressupostos de sincronia como forma de aprimorar o desempenho de Paxos. Trata-se de incorporar a um algoritmo essencialmente assíncrono abordagens empregadas em modelos mais restritivos, como o modelo síncrono. Esta tese relata os resultados obtidos a partir da abordagem de agregar hipóteses de sincronia a Paxos como forma de aprimorar seu desempenho. Nossas contribuições podem ser sintetizadas da seguinte forma. Primeiramente, mostramos que uma rede local, dado que a ela se apliquem mecanismos de controle de carga, se comporta na maior parte do tempo de forma predominantemente síncrona. Este resultado é atestado por, e propiciou o desenvolvimento de dois algoritmos de difusão totalmente ordenada. O Time Hybrid Total Order Broadcast (THyTOB) representa a possiblidade efetiva de se implementar um algoritmo de difusão totalmente ordenada essencialmente síncrono que opera sobre um sistema tipicamente modelado como assíncrono. THyTOB não apenas apresenta um desempenho, na ausências de falhas, superior a implementações tradicionais de Paxos, como também se destacou por sua reduzida variação de latências: é um algoritmo estável com desempenho bastante previsível. Apresentamos também nosso On-Time Fast Paxos, um algoritmo que usa tempo para gerar uma ordenação total para a as mensagens, que é então ratificada por instâncias de Fast Paxos. On-Time Fast Paxos apresenta altas vazões, da ordem da capacidade da rede, enquanto provê latências baixas e bem condicionadas. Trata-se da comprovação de nossa tese: sincronia melhora o desempenho de Paxos

Abstract: Algorithms of consensus and of total order broadcast are central for the implementation of fault-tolerant distributed applications. Paxos is an asynchronous consensus algorithm commonly used to implement total order broadcast. Briefly, Paxos provides that messages sent to a set of processes are delivered by them in the same total order. A functionality that is simple to implement under the normal operation of a distributed system, but which becomes admittedly complicated when a mix of asynchrony and failures is observed. The asynchronous design of Paxos aims to secure a consistent behavior under a particularly adverse ensemble of operating conditions: robustness is its major attribute. But when it comes to the regular, fail-free and predominantly synchronous, operation of the system, Paxos fails to deliver a performance compatible with the available resources. The quest for ways to improve the performance of Paxos gains importance when the algorithm progressively becomes part of the core of multiple replication solutions. In fact, several variations of Paxos designed for achieving high-performance total order broadcast were proposed in parallel with our PhD research. They address limitations of the original algorithm and suggest changes, from the reorganization of the topology to optimizations in the use of the network by the processes. Our approach differs from existing, or parallel approaches because it involves the explicit adoption of synchrony assumptions as a way to improve performance of Paxos. This is about incorporating to an essentially asynchronous algorithm approaches adopted by stricter models, such as the synchronous model. This thesis reports the results achieved from the approach of augmenting Paxos with synchronous assumptions as a way to improve its performance. Our contributions can be summarized as follows. First, we demonstrate that a local area network, given that load control mechanisms are adopted, behaves in a predominantly synchronously manner most of the time. This result is attested by, and lead to the development of two total order broadcast algorithms. Our Time Hybrid Total Order Broadcast (THyTOB) represents the ability of implementing an essentially synchronous total order broadcast algorithm atop of a system typically modelled as asynchronous. THyTOB not only performs, in the absence of failures, better than traditional implementations of Paxos, but also has a very low latency variation: it is a stable and very predictable algorithm. Then we have On-Time Fast Paxos, an algorithm that uses time to generate a total order for the broadcast messages, which is ratified by instances of Fast Paxos. On-Time Fast Paxos sports high throughput, close the network capacity, while providing low and conditioned latencies. This proves our thesis: synchrony actually improves the performance of Paxos
Subject: Sistemas distribuídos
Tolerância à falha (Computação)
Consenso distribuído (Computação)
Algoritmos de ordenação total
Sincronização
Language: Inglês
Editor: [s.n.]
Citation: CASON, Daniel. The role of synchrony on the performance of Paxos: O papel da sincronia no desempenho de Paxos. 2017. 1 recurso online (100 p.). Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/332151>. Acesso em: 5 set. 2018.
Date Issue: 2017
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Cason_Daniel_D.pdf1.15 MBAdobe PDFView/Open


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