Export this record: EndNote BibTex

Please use this identifier to cite or link to this item: https://tede2.pucrs.br/tede2/handle/tede/9165
Document type: Dissertação
Title: Enhancing early scheduling in parallel state machine replication
Author: Batista, Eliã Rafael de Lima 
Advisor: Dotti, Fernando Luís
First advisor-co: Pedone, Fernando
Abstract (native): State machine replication is a well-established approach to provide fault tolerance. One of its key assumptions is that eplicas must execute operations deterministically and thus serially. However, to benefit from multi-core servers, some techniques were built to allow concurrent execution of operations in state machine replication. Invariably, such techniques are based on the fact that independent operations (which do not share common state or do not update shared state) can execute in parallel. Early Scheduling is a promising technique that trades concurrency for expeditious scheduling decisions. In this technique, requests are grouped in classes and a fixed subset of threads is assigned to each class, respecting request dependencies. Early scheduling has been shown to provide significant performance improvements in state machine replication. Although early scheduling shows performance gains, it restricts concurrency according to the class definitions and class-to-threads mapping. We evaluate the impact of these restrictions imposed by the early scheduling technique. Out of the observations, we propose and implement improvements to the basic technique, present their results and compare the resulting system to more classic approaches. Our main contribution concern the use of alternative synchronization techniques, such as busy wait adaptations and application of work-stealing techniques within the former Early Scheduling algorithm.
Abstract (english): 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.
Keywords: Escalonamento antecipado
Replicação máquina de estados
Roubo de trabalho
Espera ocupada
Early Scheduling
State machine replication
Work-stealing
Busy-wait
CNPQ Knowledge Areas: CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
Language: eng
Country: Brasil
Publisher: Pontifícia Universidade Católica do Rio Grande do Sul
Institution Acronym: PUCRS
Department: Escola Politécnica
Program: Programa de Pós-Graduação em Ciência da Computação
Access type: Acesso Aberto
Fulltext access restriction: Trabalho não apresenta restrição para publicação
URI: http://tede2.pucrs.br/tede2/handle/tede/9165
Issue Date: 18-Mar-2020
Appears in Collections:Programa de Pós-Graduação em Ciência da Computação

Files in This Item:
File Description SizeFormat 
ELIÃ RAFAEL DE LIMA BATISTA_DIS.pdfELIÃ_RAFAEL_DE_LIMA_BATISTA_DIS2.09 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.