Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/7520
Título: | Agregação e contagem em redes P2P |
Autor(es): | Jesus, Paulo César de Oliveira |
Orientador(es): | Baquero, Carlos Almeida, Paulo Sérgio |
Data: | 28-Set-2007 |
Resumo(s): | A agregação tem um papel importante na implementação de sistemas distribuídos,
nomeadamente em rede P2P (peer-to-peer ), permitindo a obtenção de
propriedades globais (tais como o tamanho da rede, ou a temperatura média
de uma rede de sensores). Estes valores globais podem por sua vez, ser utilizados
na execução de operações basilares para o funcionamento do sistema.
Embora aparentemente simples, a agregação tem-se revelado um problema
difícil e interessante, quando se procura soluções em ambientes distribuídos,
onde não existe um único elemento central com uma visão global do sistema.
Este estudo descreve diversas soluções para o problema da agregação,
sendo proposta e avaliada uma nova solução para este problema. Esta dissertação
oferece duas contribuições científicas relevantes acerca deste tema.
A primeira contribuição consiste na apresentação de uma taxonomia das principais
técnicas e mecanismos de agregação existentes, sendo esta dividida de
acordo com dois aspectos principais: comunicação (referindo os protocolos e
estruturas de comunicação usados) e computação (citando os fundamentos e
princípios de computação nos quais os algoritmos se baseiam).
A segunda e mais importante contribuição deste estudo consiste na apresentação
de uma nova solução para o problema da agregação e contagem
(determinação do tamanho da rede). O novo algoritmo proposto — Flow
Updating — evidencia um melhor desempenho global que os algoritmos anteriores
da mesma categoria — averaging, assumindo-se como a melhor solução
em termos de velocidade de execução e custos de comunicação. Mais
importante, é a introdução de uma abordagem que lhe permite uma efectiva
tolerância a faltas, sendo esta uma característica que não foi encontrada nos
algoritmos de averaging anteriores. Aggregation plays an important role in the implementation of distributed systems, namely in P2P (peer-to-peer) networks, providing the summary of global properties (like the network size, or the average temperature read by a sensor network). These global values can be used to perform key operations during system execution. Although apparently simple, aggregation has reveled to be a hard, and rich, problem when seeking solutions in distributed environments, with no single element holding a global vision of the system. This study describes several solutions for the aggregation problem, and, as well, presents and evaluates a new solution for this problem. This dissertation includes two relevant scientific contributions about this subject. The first contribution consists on a survey of the essential aggregation’s techniques and existing mechanisms, organized according two main aspects: communication (referring protocols and structures used in data communication) and computing (indicating the computing concepts and models used by the algorithms). The second and main contribution of this study describes a new solution to the aggregation and counting (network size estimation) problem. The new algorithm — Flow Updating — exhibits a better global performance than previous algorithms in the same category, averaging, proving to be the best solution in terms of execution speed and communication cost. Most important, it introduces an approach that can tolerate message losses, a property that was not found on existing averaging algorithms. |
Tipo: | Dissertação de mestrado |
Descrição: | Dissertação de Mestrado em Sistemas Móveis |
URI: | https://hdl.handle.net/1822/7520 |
Acesso: | Acesso aberto |
Aparece nas coleções: | BUM - Dissertações de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
MSM_Tese_PauloJesus.pdf | 2,47 MB | Adobe PDF | Ver/Abrir |