Submitted by Setor de Tratamento da Informa??o - BC/PUCRS (tede2@pucrs.br) on 2016-08-04T16:39:32Z
No. of bitstreams: 1
TES_ODORICO_MACHADO_MENDIZABAL_COMPLETO.pdf: 1253774 bytes, checksum: 8ab2360ff12ca83b15b415cba7eda7de (MD5) / Made available in DSpace on 2016-08-04T16:39:32Z (GMT). No. of bitstreams: 1
TES_ODORICO_MACHADO_MENDIZABAL_COMPLETO.pdf: 1253774 bytes, checksum: 8ab2360ff12ca83b15b415cba7eda7de (MD5)
Previous issue date: 2016-05-16 / A well-established technique used to design fault-tolerant systems is state machine replication. In part, this is explained by the simplicity of the approach and its strong consistency guarantees. The traditional state machine replication model builds on the sequential execution of requests to ensure consistency among the replicas. Sequentiality of execution, however, threatens the scalability of replicas. Recently, some proposals have suggested parallelizing the execution of replicas to achieve higher performance. Despite the success of parallel state machine replication in accomplishing high performance, the implication of such models on the recovery is mostly left unaddressed. Even for the traditional state machine replication approach, relatively few studies have considered the issues involved in recovering faulty replicas. The motivation of this thesis is clarifying the challenges and performance implications involved in checkpointing and recovery for parallel state machine replication. The thesis also aims to advance the state-of-the-art by proposing novel algorithms for checkpointing and recovery in the context of parallel state machine replication. Performing checkpoints efficiently in such parallel models is more challenging than in classic state machine replication because the checkpoint operation must account for the execution of concurrent commands. In this thesis, we review checkpointing techniques for parallel approaches to state machine replication and compare their impact on performance through simulation. Furthermore, we propose two checkpoint techniques for one of these parallel models. Recovering a replica requires (a) retrieving and installing an up-to-date replica checkpoint, and (b) restoring and re-executing the log of commands not reflected in the checkpoint. Parallel state machine replication render recovery particularly challenging since throughput under normal execution (i.e., in the absence of failures) is very high. Consequently, the log of commands that need to be applied until the replica is available is typically large, which delays the recovery. We present two novel techniques to optimize recovery in parallel state machine replication. The first technique allows new commands to execute concurrently with the execution of logged commands, before replicas are completely updated. The second technique introduces ondemand state recovery, which allows segments of a checkpoint to be recovered concurrently. We experimentally assess the performance of our recovery techniques using a full-fledged parallel state machine replication prototype and compare the performance of these techniques to traditional recovery mechanisms under different scenarios. / A replica??o m?quina de estados ? uma t?cnica bem estabelecida para desenvolvimento de sistemas tolerantes a faltas. Em parte, isso ? explicado pela simplicidade da abordagem e sua garantia de consist?ncia forte. O modelo de replica??o m?quina de estados tradicional baseia-se na execu??o sequencial de requisi??es para garantir consist?ncia forte entre as r?plicas. A sequencialidade da execu??o, no entanto, compromete a escalabilidade. Recentemente, algumas propostas sugeriram paralelizar a execu??o de algumas requisi??es visando um aumento na vaz?o. Apesar do sucesso da replica??o m?quina de estados paralela em obter alto desempenho, as implica??es deste modelo em procedimentos de recupera??o s?o desprezadas. Mesmo para a abordagem de replica??o m?quina de estados tradicional, poucos estudos t?m considerado as quest?es envolvidas na recupera??o de r?plicas defeituosas. A motiva??o desta tese ? elucidar os desafios e implica??es no desempenho decorrentes de mecanismos de pontos de verifica??o e recupera??o em replica??o m?quina de estados paralela. A tese tamb?m avan?a no estado-da-arte, propondo novos algoritmos para pontos de verifica??o e recupera??o no contexto de replica??o m?quina de estados paralela. Criar pontos de verifica??o de forma eficiente em tais modelos ? mais desafiador do que na replica??o m?quina de estados cl?ssica porque deve-se considerar a execu??o concorrente de comandos. Nesta tese, n?s revisitamos as t?cnicas para pontos de verifica??o em abordagens paralelas de replica??o m?quina de estados e comparamos o impacto destas no desempenho atrav?s de simula??o. Al?m disso, n?s propomos duas t?cnicas de ponto de verifica??o para um destes modelos paralelos. Recuperar uma r?plica requer: (a) obter e instalar o estado de um ponto de verifica??o de uma r?plica atualizada, e (b) recuperar e re-executar os comandos n?o refletidos no ponto de verifica??o. T?cnicas paralelas para replica??o m?quina de estado tornam a recupera??o de r?plicas particularmente dif?cil uma vez que a vaz?o de processamento durante a execu??o normal (isto ?, na aus?ncia de falhas) ? muito alta. Consequentemente, o registo de comandos que precisa ser re-executado ? tipicamente grande, o que atrasa a recupera??o. N?s apresentamos duas novas t?cnicas para otimizar a recupera??o em replica??o m?quina de estados paralela. A primeira t?cnica permite que novos comandos sejam executados em paralelo com a re-execu??o dos comandos n?o refletidos no ponto de verifica??o. Isto ocorre antes da r?plica estar completamente atualizada. A segunda t?cnica introduz recupera??o de estado sob-demanda, permitindo que segmentos de um ponto de verifica??o possam ser recuperados apenas quando necess?rios, ou ainda, concorrentemente. N?s avaliamos o desempenho de nossas t?cnicas de recupera??o usando um prot?tipo completo para replica??o m?quina de estados paralela e comparamos o desempenho destas t?cnicas com mecanismos tradicionais de recupera??o em diferentes cen?rios.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede2.pucrs.br:tede/6879 |
| Date | 16 May 2016 |
| Creators | Mendizabal, Odorico Machado |
| Contributors | Dotti, Fernando Lu?s, Pedone, Fernando |
| Publisher | Pontif?cia Universidade Cat?lica do Rio Grande do Sul, Programa de P?s-Gradua??o em Ci?ncia da Computa??o, PUCRS, Brasil, Faculdade de Inform?tica |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da PUC_RS, instname:Pontifícia Universidade Católica do Rio Grande do Sul, instacron:PUC_RS |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 1974996533081274470, 600, 600, 600, -3008542510401149144, 3671711205811204509 |
Page generated in 0.0019 seconds