Defesa de Doutorado de Daniel Cason

Data: 
31/03/2017 - 09:30
Local: 
Auditório do IC 2 - Sala 85

Título: The role of synchrony on the performance of Paxos

 

Banca Examinadora
Titulares (Professores Doutores) Unidade / Instituição
Luiz Eduardo Buzato IC/UNICAMP
Fernando Pedone Faculty of Informatics / University of Lugano
Fernando Luís Dotti FC/PUCRS
Edmundo Roberto Mauro Madeira IC/UNICAMP
Islene Calciolari Garcia IC/UNICAMP
Suplentes (Professores Doutores) Unidade / Instituição
Ricardo de Oliveira Anido IC/UNICAMP
Guido Costa Souza de Araujo IC/UNICAMP
Gustavo Maciel Dias Vieira Dcomp-So/UFSCar

 

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.