Avaliação do desempenho do particionamento de estado em Replicação Máquina de Estados Paralela

Abstract

Replicação Máquina de Estados é uma técnica amplamente utilizada para prover tolerância a falhas e consistência forte em sistemas distribuídos. Nessa abordagem todas as requisições são executadas sequencialmente, na mesma ordem total, por todas as réplicas. Buscando melhorar a vazão do sistema, versões aprimoradas foram propostas, onde requisições independentes podem ser executadas em paralelo. Existe o desafio, porém, de como balancear a carga de trabalho entre threads trabalhadoras, ao mesmo tempo em que é necessário reduzir o número de sincronizações entre threads. Algoritmos de particionamento balanceado de grafos podem ser utilizados para atingir tais objetivos em sistemas paralelos e distribuídos. Esse trabalho apresenta um modelo de execução de Replicação Máquina de Estados Paralela que utiliza o particionamento balanceado de grafos, buscando balancear requisições e reduzir sincronizações entre threads em uma réplica arbitrária. Além disso, é apresentado um estudo que explora como a escolha do algoritmo de particionamento pode impactar o desempenho do sistema. Os resultados obtidos sugerem que ganhos de desempenho são possíveis, sendo altamente dependentes da característica da carga de trabalho, da frequência de reparticionamento, e algoritmo escolhido.