Robust distributed data aggregation

Abstract

Distributed aggregation algorithms are an important building block of modern large scale systems, as it allows the determination of meaningful system-wide properties (e.g., network size, total storage capacity, average load, or majorities) which are required to direct the execution of distributed applications. In the last decade, several algorithms have been proposed to address the distributed computation of aggregation functions (e.g., COUNT, SUM, AVERAGE, and MAX/MIN), exhibiting different properties in terms of accuracy, speed and communication tradeoffs. However, existing approaches exhibit many issues when challenged in faulty and dynamic environments, lacking in terms of fault-tolerance and support to churn. This study details a novel distributed aggregation approach, named Flow Updating, which is fault-tolerant and able to operate on dynamics networks. The algorithm is based on manipulating flows (inspired by the concept from graph theory), that are updated using idempotent messages, providing it with unique robustness capabilities. Experimental results showed that Flow Updating outperforms previous averaging algorithms in terms of time and message complexity, and unlike them it self adapts to churn and changes of the initial input values without requiring any periodic restart, supporting node crashes and high levels of message loss. In addition to this main contribution, others can also be found in this research work, namely: a definition of the aggregation problem is proposed; existing distributed aggregation algorithm are surveyed and classified into a comprehensive taxonomy; a novel algorithm is introduced, based on Flow Updating, to estimate the Cumulative Distribution Function (CDF) of a global system attribute. It is expected that this work will constitute a relevant contribution to the area of distributed computing, in particular to the robust distributed computation of aggregation functions in dynamic networks.

Os algoritmos de agregação distribuídos têm um papel importante no desenho dos sistemas de larga escala modernos, uma vez que permitem determinar o valor de propriedades globais do sistema (e.g., tamanho da rede, capacidade total de armazenamento, carga média, ou maiorias) que são fundamentais para a execução de outras aplicações distribuídas. Ao longo da última década, diversos algoritmos têm sido propostos para calcular funções de agregação (e.g., CONTAGEM, SOMA, M´E DIA, ou MIN/MAX), possuindo diferentes características em termos de precisão, velocidade e comunicação. No entanto, as técnicas existentes exibem vários problemas quando executadas em ambientes com faltas e dinâmicos, deixando a desejar em termos de tolerância a faltas e não suportando a entrada/saída de nós. Este estudo descreve detalhadamente uma nova abordagem para calcular funções de agregação de forma distribuída, denominada Flow Updating, que é tolerante a faltas e capaz de operar em redes dinámicas. O algoritmo é baseada na manipulacão de fluxos (inspirado no conceito da teoria de grafos), que são atualizados por mensagens idempotentes, conferindo-lhe capacidades unicas em termos de robustez. Os resultados experimentais demonstram que o Flow Updating supera os anteriores algoritmos baseados em técnicas de averaging em termos de complexidade de tempo e mensagens, e, ao contrário destes, auto adapta-se a mudanc¸as da rede (i.e., entrada/saída de nós e alteraçãoo dos valores iniciais) sem necessitar de reiniciar periodicamente a sua execuçãoo, suportando falhas de nos e elevados níveis de perdas de mensagens. Para além desta contribuição principal, outras são também encontradas neste trabalho, nomeadamente: é proposta uma definição do problema da agregação; é descrito o estado da arte em termos dos algoritmos de agregação distribuídos, e estes são classificados numa taxonomia abrangente; é apresentado um novo algoritmo baseado no Flow Updating para estimar a Funcão de Distribuição Cumulativa (CDF) de um atributo global do sistema.