Enhancing early scheduling in parallel state machine replication

• Ano de defesa: 2020
• Autor(a) principal: Batista, Eliã Rafael de Lima
• Orientador(a): Dotti, Fernando Luís
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Pontifícia Universidade Católica do Rio Grande do Sul
• Programa de Pós-Graduação: Programa de Pós-Graduação em Ciência da Computação
• Departamento: Escola Politécnica
• País: Brasil
• Palavras-chave em Português: Escalonamento antecipado; Replicação máquina de estados; Roubo de trabalho; Espera ocupada
• Palavras-chave em Inglês: Early Scheduling; State machine replication; Work-stealing; Busy-wait
• Área do conhecimento CNPq: CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://tede2.pucrs.br/tede2/handle/tede/9165

Replicação Máquina de Estados é uma abordagem bem difundida cujo objetivo é fornecer tolerância a falhas em sistemas distribuídos. Baseia-se na ideia de que réplicas devem executar operações de forma determinística e, portanto, sequencial. No entanto, para se beneficiar de arquiteturas multi-core, técnicas têm sido propostas para permitir execução paralela. Elas se baseiam no fato de que operações independentes (que não compartilham nem alteram estado compartilhado) podem executar em paralelo. Early Scheduling (escalonamento antecipado) é uma técnica promissora que abre mão de concorrência em troca de rápidas decisões de escalonamento. Nela, requisições são agrupadas em classes, e um sub-conjunto de threads é atribuído a cada classe, respeitando dependências entre requisições. Early Scheduling apresentou ganhos significativos de performance em replicação máquina de estados, apesar das restrições impostas pelas definições de classes e mapeamentos para threads. Neste trabalho avaliamos os impactos causados por tais restrições. A partir dos resultados observados, propomos e implementamos melhorias, apresentamos os resultados e comparamos com outras abordagens clássicas. Nossa contribuição se dá no uso de técnicas de sincronização alternativas, como adaptações de espera ocupada e aplicação de conceitos de work-stealing (roubo de trabalho) ao algoritmo original.