Uma solução autonômica para k-exclusão mútua em sistemas distribuídos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorDuarte Junior, Elias Procopio-
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorRodrigues, Luiz Antonio-
Data de aceite: dc.date.accessioned2019-08-22T00:22:02Z-
Data de disponibilização: dc.date.available2019-08-22T00:22:02Z-
Data de envio: dc.date.issued2014-10-24-
Data de envio: dc.date.issued2014-10-24-
Data de envio: dc.date.issued2014-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/1884/36459-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/36459-
Descrição: dc.descriptionOrientador : Prof. Dr. Elias P. Duarte Jr.-
Descrição: dc.descriptionTese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 12/08/2014-
Descrição: dc.descriptionInclui referências-
Descrição: dc.descriptionResumo: Uma das grandes vantagens dos sistemas distribuídos é o compartilhamento de recursos. No entanto, diversos processos podem solicitar o acesso a um recurso compartilhado de forma concorrente e, em certos casos, é necessário garantir que um único processo obtenha permissão de acesso ao recurso em cada instante de tempo. Para tanto, são utilizados os algoritmos de exclusão mútua. Nas soluções que utilizam pedidos de permissão, cada processo deve solicitar aos demais a permissão para utilizar o recurso, A permissão deve ser obtida de todos os processos ou de um subconjunto deles, como definido pelas soluções com quóruns. Uma extensão do problema da exclusão mútua é a k-exclusão mútua. Nesta categoria, ao invés de um, existem k cópias idênticas do recurso compartilhado. O objetivo é garantir que, no máximo, k processos obtenham acesso aos recursos de cada vez. As soluções de k-exclusão mútua existentes são basicamente adaptadas dos algoritmos de 1-exclusão mútua. Entretanto, a maior parte destas soluções não aborda a questão da ocorrência de falhas no sistema. Nesta tese é proposta uma solução autonômica de k-exclusão mútua distribuída que opera corretamente para até n — 1 processos falhos, sendo n o total de processos no sistema. O algoritmo de k-exclusão mútua é baseado em algoritmos hierárquicos de difusão (broadcast), também propostos nesta tese, O objetivo de desenvolver estes algoritmos é otimizar a propagação das mensagens de requisição de recursos do algoritmo de exclusão mútua. Dois algoritmos de difusão foram propostos, um para difusão de melhor-esforço e outro para difusão confiável. Estes algoritmos são baseados em uma outra solução também proposta neste trabalho: um algoritmo autonômico e hierárquico para a construção e manutenção de árvores geradoras (spanning trees). As árvores são construídas de forma totalmente distribuída e adaptativa sobre uma topologia de hipercubo virtual, denominada Vcube. A estratégia proposta é eficiente e escalável, além de tolerar até n — 1 falhas de processo. As soluções propostas são também autonômicas no sentido que se adaptam automaticamente frente à ocorrência de falhas, reorganizando os elementos corretos do sistema. Uma segunda abordagem foi proposta para o problema da exclusão mútua, um algoritmo de quóruns, também construído sobre a topologia VCube, A carga e o tamanho dos quóruns são balanceados, mesmo após a ocorrência de falhas. Todos os algoritmos propostos são descritos, especificados e foram implementados através de simulação. São apresentadas provas de correção e resultados experimentais para todas as propostas.-
Descrição: dc.descriptionAbstract: One of the key purposes of distributed systems is to allow resources to be shared. Howe­ver, several processes can request access to a shared resource concurrently and in some eases it is necessary to ensure that only a single process has permission to access the resource per instant of time. Mutual exclusion algorithms are used for this purpose. In permission-based solutions, each process must request permission to others before acces­sing the resource. The permission must be obtained for all processes or a subset of them, as is the ease when quorum-based solutions are employed. An extension of the mutual exclusion problem is k-mutual exclusion. In this case, instead of one, there are k identical copies of the shared resource. The main issue is to ensure that at most k processes get k adaptations of algorithms for mutual exclusion of a single resource. However, most of these solutions do not address the question of the oeeurrenee of faults in the system. In this thesis an autonomic solution for distributed k-mutual exclusion is proposed that works correctly even if up to n — 1 processes are faulty, assuming that the svstem consists of n k algorithms also proposed in this thesis. The purpose for developing these algorithms is to optimize the propagation of request messages used by the mutual exclusion algorithm. Two hierarchical broadcast algorithms were proposed, one for best-effort broadcast and another for reliable broadcast. These broadcast algorithms are based on yet another building block that was proposed in this thesis: an autonomic hierarchical algorithm for building and maintaining spanning trees. The spanning trees are constructed in a fully distributed and adaptive way on a virtual hypercube-like topology, called VCube, The n — 1 processes. The proposed solutions are also autonomic in the sense that they adapt them­selves automatically after the oeeurrenee of faults by reorganizing the correct processes remaining in the system, A second approach was also proposed for the mutual exclusion problem, a quorum-based algorithm, also built on the VCube topology. The load and size of the quorums are kept balanced, even after faults. All proposed algorithms are described, specified and have been implemented by simulation. Proofs of correctness and experimental results for all proposals are presented.-
Formato: dc.format106f. : il., tabs., grafs., color.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectTeses-
Palavras-chave: dc.subjectSistemas de reconhecimento de padrões-
Palavras-chave: dc.subjectCiência da computação-
Título: dc.titleUma solução autonômica para k-exclusão mútua em sistemas distribuídos-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.