Consenso em Memória Compartilhada Dinâmica

Abstract

Sistemas distribuídos modernos, sobre redes móveis ad-hoc, entre pares (P2P), grades oportunistas ou nuvens, permitem que seus participantes acessem serviços e informações independente de sua localização ou topologia da rede. Garantir tais serviços exige um projeto de sistema confiável completamente distribuído e que possa lidar com o dinamismo, falhas e falta de conhecimento global. Esta tese dedica-se ao estudo de dois problemas fortemente relacionados e que são fundamentais no desenvolvimento de sistemas distribuídos confiáveis: o problema do consenso e o problema da eleição de líder após um tempo, considerando um ambiente assíncrono, dinâmico, em que os processos entram e saem do sistema aleatoriamente, se comunicam através de uma memória compartilhada e podem falhar por parada. A maioria das propostas para esses problemas foca em sistemas estáticos onde o conjunto de participantes é conhecido e fixo, e a comunicação se dá por passagem de mensagens. Entretanto, classes importantes de sistemas como os serviços centrados em dados tolerantes a falhas e altamente disponíveis, além das máquinas com arquitetura multinúcleo, onde os processos compartilham uma única memória física, não se adequam a esse modelo. No primeiro caso, algumas aplicações relevantes são as redes de área de armazenamento (SANs); sistemas de armazenamento P2P Bizantinos; e sistemas de passagem de mensagem nos quais servidores são modelados como componentes de armazenamento. Nesta tese, é proposto um conjunto de algoritmos para o problema do consenso tolerante a falhas em sistemas assíncronos com memória compartilhada, onde o conjunto de participantes é desconhecido. Duas abordagens são exploradas. A primeira considera a abstração detector de participantes que auxilia na construção do conhecimento do sistema. A solução conta com um algoritmo de consenso genérico baseado em oráculo que, ao que se sabe, é o primeiro algoritmo de consenso para memória compartilhada que pode ser instanciado com um detector de falhas da classe ◊S, ou um detector de líder da classe Ω. A segunda apresenta um consenso genérico com outra característica inovadora: não depende do conhecimento da cardinalidade do conjunto de participantes, de modo que suporta o dinamismo do sistema. Ainda na direção de prover serviços fundamentais para ambientes dinâmicos de memória compartilhada, propõe-se um protocolo de detecção de líder após um tempo. O algoritmo é livre de tempo, no sentido de que não usa temporizadores para garantir a convergência. Ao invés disso, baseia-se num padrão de acesso à memória compartilhada. Ao que se sabe, é o primeiro algoritmo a implementar um serviço de líder ? para memória compartilhada livre de tempo. Na prática, um consenso genérico e modular é um arcabouço que permite construir sistemas dinâmicos de camadas superiores independentes do detector de falhas que está disponível. Nesse caso, a implementação do consenso pode ser melhor adaptada às características particulares de cada ambiente; principalmente quando a implementação do detector serve a muitas aplicações. Desse modo, as aplicações existentes, que já estão rodando sobre os detectores ◊S ou Ω, podem ser portadas mais facilmente.