Redução dos efeitos negativos das suspeitas incorretas no algoritmo de consenso de Chandra e Toueg

• Ano de defesa: 2011
• Autor(a) principal: Fermino, Lucas Menezes
• Orientador(a): Sotoma, Irineu
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Algoritmos; Sistemas Distribuídos; Algoritmos Úteis e Específicos
• Link de acesso: https://repositorio.ufms.br/handle/123456789/476

Alguns protocolos na área de sistemas distribuídos, como por exemplo, atomic broadcast e replicação semi-passiva, se baseiam no algoritmo de consenso proposto por Chandra e Toueg. Esse algoritmo é equipado com um detector de falhas não confiável. Em sistemas distribuídos assíncronos, esse tipo de detector pode cometer erros ao suspeitar erroneamente de um processo que ainda está em execução. A presença de suspeitas incorretas degrada significativamente o desempenho do algoritmo e o desempenho de qualquer protocolo que o utiliza. Para minimizar essa degradação, nós propomos duas novas otimizações e uma adaptação da técnica Look-Ahead ao algoritmo. A primeira otimização, denominada Early-Decision, permite antecipar uma decisão para o problema de consenso. A segunda otimização, denominada Additional-Waiting, permite estender o tempo de espera por mensagens quando for útil. A técnica Look-Ahead ajuda a acelerar a execução do consenso quando existem processos em diferentes rodadas. Nós apresentamos a descrição do algoritmo que combina essas otimizações, e provamos a sua corretude. Nós realizamos uma série de simulações para avaliar os efeitos das otimizações sobre o desempenho do algoritmo de Chandra e Toueg. Além disso, nós comparamos o desempenho de alguns algoritmos de consenso e selecionamos o melhor, o algoritmo de Paxos, para ser comparado com o algoritmo de Chandra e Toueg otimizado. Os resultados das simulações mostram que todas as otimizações são eficazes, principalmente, quando são combinadas. Na maioria das situações consideradas, o desempenho do algoritmo de Chandra e Toueg otimizado é melhor que o do algoritmo de Paxos.