You are here

Miguel Silva defende dissertação de mestrado intitulada "Estimativa de funções de probabilidade cumulativa em redes de larga escala"

A prova de Mestrado em Engenharia Informática, requerida por Miguel Ângelo Borges da Silva e subordinada ao tema "Estimativa de funções de probabilidade cumulativa em redes de larga escala", realiza-se no dia 30 de novembro de 2011 pelas 09h30, no anfiteatro A2 do Departamento de Informática. A sessão é aberta a todos os interessados.

O júri para esta prova tem a seguinte composição:

  • António Costa (UMinho) - presidente
  • Nuno Lopes (IPCA) - arguente
  • Carlos Baquero (UMinho) – orientador

Resumo da dissertação

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.

11.11.2011

início contactos RSS Feed última actualização: 21-Set-2018 partilhar facebook
Drupal theme by pixeljets.com D7 ver.1.1