Defesa de Doutorado de Daniel Cason

Título do Trabalho
The role of synchrony on the performance of Paxos
Candidato(a)
Daniel Cason
Nível
Doutorado
Data
Add to Calender 2017-03-31 00:00:00 2017-03-31 00:00:00 Defesa de Doutorado de Daniel Cason The role of synchrony on the performance of Paxos Auditório do IC 2 - Sala 85 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
9:30
Local
Auditório do IC 2 - Sala 85
Orientador(a)
Luiz Eduardo Buzato
Banca Examinadora

Titulares:
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:
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.