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 todos os comandos são executados sequencialmente, na mesma ordem total, por todas as réplicas. Buscando melhoras na vazão do sistema, versões aprimoradas foram propostas, onde comandos independentes podem ser executados em paralelo. Existe o desafio, porém, de balancear a carga de trabalho entre threads trabalhadoras, ao mesmo tempo que é necessário reduzir sincronizações entre as threads. No contexto de sistemas distribuídos e escalonamento, o problema de Partição Balanceada de Grafos visa balancear trabalho e reduzir comunicação entre diferentes máquinas de um sistema. Neste trabalho, foi investigado o desempenho e qualidade da solução obtida com diferentes algoritmos para particionamento balanceado de grafos. Particularmente no contexto de Replicação Máquina de Estados, as estratégias de particionamento investigadas são usadas para distribuir requisições para threads trabalhadoras em uma réplica individual.