Um algoritmo de disseminação filtrada baseado em super nós e na redundância de filtros

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Os sistemas Editor/Assinante baseados no conteúdo têm como objectivo fazer chegar mensagens, ou notificações, somente aos participantes que expressaram interesse nesses dados específicos. Para tal, esta forma de difusão de informação, dita filtrada, recorre a filtros que inspeccionam o conteúdo das mensagens, de modo a seleccionar aquelas que contêm os padrões desejados, descartando-se as demais. Esta abordagem potencia comunicações mais eficientes, pois procura não encaminhar mensagens para as quais não há receptores. E do ponto de vista do receptor, evita-se perder tempo com mensagens não desejadas, algo que é cada vez mais importante num mundo onde a informação que nos chega cresce incessantemente. A difusão filtrada tem-se revelado um problema difícil, em particular quando realizada com base em soluções descentralizadas. Muitas das dificuldades prendem-se com os problemas decorrentes da escala e do dinamismo da rede de participantes. O trabalho apresentado nesta dissertação, explora a redundância dos filtros, como forma de mitigar o impacto negativo da escala e de uma taxa excessiva de entrada de novos participantes. Partindo de uma solução existente, baseada no conhecimento completo de todos os nós da rede, a nova solução proposta organiza a rede de disseminação em duas camadas. Na camada superior, povoada por super-nós, está representado o conjunto de filtros únicos no sistema, enquanto que participantes com filtros repetidos na rede são relegados para o nível inferior. Esta solução traduz-se em custos que dependem maioritariamente do ritmo de chegada de participantes cujos filtros ainda não estão representados no sistema, o que na presença de redundância significativa, tenderá a ser bastante inferior que ao custo original. Complementarmente, foram também desenvolvidos e avaliados experimentalmente mecanismos de tolerância a falhas, de modo a garantir a entrega fiável de mensagens com elevada probabilidade.