Agregação e contagem em redes P2P

Abstract

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.