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

Abstract

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.

Some protocols in distributed systems, such as atomic broadcast and semi-passive replication, are based on the consensus algorithm proposed by Chandra and Toueg. This algorithm is equipped with an unreliable failure detector. In asynchronous distributed systems, this type of detector can make mistakes by erroneously suspecting a process that is still running. The presence of wrong suspicions degrades significantly the performance of the algorithm and the performance of any protocol that uses it. To reduce this degradation, we propose two new optimizations and an adaptation of the Look-Ahead technique to the algorithm. The first optimization, named Early-Decision, allows to antecipate a decision to the consensus problem. The second optimization, named Additional-Waiting, allows extending the waiting time for messages when it is useful. The Look-Ahead technique helps speed up the execution of consensus when there are processes in different rounds. We present a description of the algorithm that combines these optimizations and prove its correctness. We conducted some simulations to evaluate the effects of optimizations on the performance of the algorithm. In addition, we compared the performance of some consensus algorithms and selected the most efficient, the Paxos algorithm, to be compared with the Chandra and Toueg optimized algorithm. The simulation results show that all optimizations are effective, particularly, when they are combined. In most situations considered, the performance of the Chandra and Toueg optimized algorithm is better than the Paxos algorithm.