A carregar...
Publicação
Gossip-based broadcast protocols
Autores
Orientador(es)
Resumo(s)
Gossip, or epidemic, protocols have emerged as a powerful strategy to implement highly scalable and resilient reliable broadcast primitives. Due to scalability reasons, each participant in a gossip protocol maintains only a partial view of the system, from which they select peers to perform gossip exchanges. On the other hand the natural redundancy of gossip protocols makes them less efficient than other approaches that rely in some sort of structured overlay network. The thesis addresses gossip protocols and the problem of building partial views to support their operation. For that purpose, the thesis presents and evaluates a new scalable membership protocol, which is called HyParView, that provides a number of properties, such as degree distribution, accuracy and clustering coefficient, that are highly useful to the construction of efficient gossip protocols. The thesis also introduce two new gossip protocols, based on HyParView, that provide high reliability with small message redundancy. One is an eager push gossip protocol while the other is a tree based gossip broadcast protocol. Simulations results show that, in comparison with other existing protocols, HyParView-based gossip protocols not only provide better reliability but also support higher percentages of node failures, and are able to recover faster from these failures.
Os protocolos de rumor (gossip), também chamados de epidémicos, emergiram recentemente como uma estratégia viável para a concretização de primitivas de difusão altamente escaláveis e resilientes. Por maior capacidade de escala, cada participante num protocolo de rumor mantêm apenas uma vista parcial de todo o sistema, a partir da qual efectua a selecção dos nós com os quais realiza troca de rumores. Por outro lado, a redundância natural destes protocolos tornam-nos menos eficientes do que outras abordagens que se baseiam na utiliza-ção de redes sobrepostas com estrutura. Esta tese aborda protocolos de disseminação epidémica e o problema da construção de vistas parciais para suportar a sua operação. Com esse fim, a tese apresenta e avalia um novo protocolo escalável de filiação denominado HyParView, que oferece várias propriedades, como a distribuição de grau, exactidão e coeficiente de agrupamento, que são bastante úteis na construção de protocolos de disseminação epidémica eficientes. Esta tese introduz também dois novos protocolos de disseminação epidémica baseados no HyParView, que oferecem elevada confiabilidade produzindo um número reduzido de mensagens redundantes. Um destes protocolos baseia-se na utilização de “eager push” enquanto que o outro baseia-se na utilização de uma árvore de disseminação epidémica. Resultados obtidos através de simulações mostram que, quando comparado com outros protocolos existentes, os protocolos de disseminação epidémica baseados no HyParView, não só conseguem garantir melhores valores de confiabilidade mas também exibem um tempo de recuperação às falhas inferior.
Os protocolos de rumor (gossip), também chamados de epidémicos, emergiram recentemente como uma estratégia viável para a concretização de primitivas de difusão altamente escaláveis e resilientes. Por maior capacidade de escala, cada participante num protocolo de rumor mantêm apenas uma vista parcial de todo o sistema, a partir da qual efectua a selecção dos nós com os quais realiza troca de rumores. Por outro lado, a redundância natural destes protocolos tornam-nos menos eficientes do que outras abordagens que se baseiam na utiliza-ção de redes sobrepostas com estrutura. Esta tese aborda protocolos de disseminação epidémica e o problema da construção de vistas parciais para suportar a sua operação. Com esse fim, a tese apresenta e avalia um novo protocolo escalável de filiação denominado HyParView, que oferece várias propriedades, como a distribuição de grau, exactidão e coeficiente de agrupamento, que são bastante úteis na construção de protocolos de disseminação epidémica eficientes. Esta tese introduz também dois novos protocolos de disseminação epidémica baseados no HyParView, que oferecem elevada confiabilidade produzindo um número reduzido de mensagens redundantes. Um destes protocolos baseia-se na utilização de “eager push” enquanto que o outro baseia-se na utilização de uma árvore de disseminação epidémica. Resultados obtidos através de simulações mostram que, quando comparado com outros protocolos existentes, os protocolos de disseminação epidémica baseados no HyParView, não só conseguem garantir melhores valores de confiabilidade mas também exibem um tempo de recuperação às falhas inferior.
Descrição
Tese de mestrado em Engenharia Informática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2007
Palavras-chave
Membership protocols Gossip protocols Reliable broadcast Fault tolerance Teses de mestrado - 2007