Estimativa de funções de probabilidade cumulativa em redes de larga escala

Abstract

A capacidade de agregar dados é uma característica fundamental na conceção de sistemas de informação escaláveis, que permite a determinação de propriedades globais importantes de forma descentralizada, para a coordenação de aplicações distribuídas, ou para fins de monitorização.

Agregados simples como mínimos/ máximos, contagens, somas e médias foram já extensivamente estudados no passado. No entanto, este tipo de agregados pode não ser suficiente para caracterizar distribuições de dados enviesadas e na presença de valores atípicos (outliers), tornando-se então relevante a determinação de uma estimativa dos valores na rede (e.g. histograma, função de distribuição cumulativa), dado que métricas como médias ou desvio padrão escondem em muitos casos alterações na propriedade monitorizada que são relevantes para decisão de controlo.

São ainda relativamente escassos os trabalhos que se focam sobre a agregação de métricas mais expressivas. Uma proposta recente nesse domínio [SNSP10] refere atingir uma precisão nas estimativas superior à atingida em abordagens anteriores. Trata-se de um algoritmo para a determinação de funções cumulativas de distribuições.

Apesar do contributo, essa proposta mostra limitações na tolerância a faltas e no suporte à monitorização contínua de propriedades, dado que para acompanhar alterações dos valores amostrados, a estratégia usada exige que o protocolo seja reiniciado periodicamente. Para além disso, os pressupostos dessa abordagem não admitem a perda de mensagens nem a sua duplicação.

Assim, e tomando como ponto de partida o actual estado da arte, é apresentado nesta tese um algoritmo distribuído para a determinação de funções cumulativas de probabilidade em redes de larga escala. As suas principais vantagens são a imunidade à perda de mensagens, a velocidade de convergência e a precisão que se obtém na aproximação à distribuição original. É simultaneamente adaptável a alterações no valor amostrado e resiliente a dinamismo no número de nodos na rede. Usa também um mecanismo de quiesciência dos nodos assim que a variação local da estimativa é inferior a um determinado limiar. Nessa circunstância, o nodo deixa de transmitir. Isto leva à diminuição do número de mensagens trocadas entre nodos.

As distribuições determinadas em todos os nodos permitem a tomada de decisões que tirem partido do facto de se estar a agregar uma função probabilística. Assim o nodo pode excluir outliers ou observar determinados quantis da propriedade. Para além disso, cada nodo da rede possui uma estimativa global sobre o estado geral da propriedade distribuída, o que lhe permite também a tomada de decisões com base em conhecimento local.

São apresentados nesta tese resultados de simulação que confirmam a validade da abordagem seguida. É também apresentada uma revisão da literatura relacionada cujo âmbito incluiu as técnicas mais representativas da agregação de dados para métricas escalares e as técnicas de agregação de dados para métricas complexas.

The ability to aggregate data is a fundamental feature in the design of scalable information systems, which allows the estimation of relevant global properties in a decentralized way in order to coordinate distributed applications, or for monitoring purposes. Simple aggregates such as minima/ maxima, counts, sums and averages have been thoroughly studied in the past. Nonetheless, this kind of aggregates may not be comprehensive enough to characterize biased data distributions and in presence of outliers, making the case for richer estimates of the values on the network (e.g. histograms, cumulative distributed functions), since scalar metrics like average or standard deviation hide in many cases changes in the property that are relevant to the control decision. The amount of scienti c work is relatively scarce in what concerns more expressive aggregation metrics. A recent proposal within this domain [SNSP10] claims to obtain estimates with a better precision than in previous approaches. It is an algorithm for the estimation of cumulative distribution functions. Despite the contribution, the proposal mentioned above is not fault tolerant and is also not sensible to the continuous variation of the sampled properties, for it demands the protocol to be restarted frequently in order to achieve quasi-continuous monitoring. Besides, the approach does also not admit loss or duplication of messages. Having this scenario as a starting point, this work presents a distributed algorithm for the estimation of cumulative distribution functions over large scale networks of which the main advantages are immunity to message loss, convergence speed and precision of the estimate. It can also cope with changes of the sampled property and is resilient to churn. It has also a quiescence mechanism that allows nodes to minimize communication cost by not exchanging redundant messages, whenever local variations of the estimate fall below a speci ed threshold. The estimated cumulative distribution function allows nodes to take advantage of having a broader view of the properties on the network: they may exclude outliers or monitor particular quantiles of a property. Also, each and every node of the network has a local vision of the global state of the property, thus allowing nodes to make decisions based on local knowledge. This thesis presents simulation results that support and validate the proposed approach. It also presents a state of the art that includes both representative techniques for scalar aggregates and representative techniques for complex aggregates.