• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

jcosta

Algoritmo Epidémico (Sistemas Distribuidos) - Dúvida

6 mensagens neste tópico

Boas! Neste momento tenho um projecto em mãos que envolve algoritmos epidémicos.

Basicamente temos 2000 nós estáticos, em que cada nó conhece no máximo 20 nós diferentes (esses 20 podem variar ao longo do tempo).

Cada nó tem um valor aleatório associado e o objectivo é calcular a média entre eles, sendo que essa média tem de ser conhecida por todos os nós (através da troca de mensagens entre eles). Ora o problema é que o algoritmo epidémico, propaga a "infecção" entre nós quase de uma maneira aleatória. Por exemplo, imaginando que havia apenas 3 nós (1,2 e 3) e que o 1 enviava o seu valor para o 2 e para o 3 e o 2 enviava o seu valor para o 3, o 3 recebia então o valor do 1 e recebia o valor do 2 que entretanto já tinha contabilizado o 1 também, causando uma redundância e um cálculo errado da média.

Assim eu e o meu colega estamos com dúvidas sobre como resolver esta questão, pois todas as soluções a que chegamos obrigava a que a troca de mensagens não fosse tão aleatória e fosse um pouco mais sequencial.

Espero que alguém nos consiga ajudar.

Obrigado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não percebi muito bem o que entendes por cálculo da média (pensei que era a média dos nós a que um dado nó está ligado, mas depois como a média de um influencia a dos outros fiquei sem perceber), mas para saberes se é o mesmo valor, julgo que podes passar além do valor da média em si um ID, e depois o nó 3 tem uma lista dos IDs que já recebeu e simplesmente ignora os repetidos.

Mais uma vez, como não percebi bem o funcionamento, isto pode não fazer sentido..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Cada nó tem um valor aleatório. A média seria feita com esses valores aleatórios de todos os nós do sistema e todos os nós têm de ir conhecendo essa média ao longo do tempo. Não é muito fácil de explicar mas conforme os nós vão sendo infectados, esses nós vão conhecendo o valor da média actual até no final, estarem todos infectados e todos conhecerem a média exacta do sistema.

Quanto à ideia da estrutura, de facto já tinha pensado nisso mas a ideia do problema é os nós não conhecerem informação de mais nada sem ser os tais 20 que referi anteriormente (e mesmo assim só conhece um endpoint para comunicar com esses nós). Com essa lista os nós saberiam informação a mais.

No entanto já chegámos a uma conclusão que vamos tentar explorar que é utilizar o mínimo dos valores e ir construindo uma árvore cuja raiz seria sempre o nó com o valor mínimo. Assim todos os nós acabados de infectar, passariam para o pai na árvore os seus valores e ia se calculando a média até chegar à raiz. Posteriormente a raiz iria espalhar o valor exacto da média.

Não sei se me fiz entender perfeitamente desta vez. É que o problema é um bocado complexo de explicar.

No entanto obrigado pela ajuda. Todas as dicas serão bem vindas.  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se o grafo contiver ciclos não sei como vão construir a árvore.

E dados os limites, é bastante provável ter.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem o problema está resolvido. Conseguimos mesmo estruturar os nós numa espécie de árvore. Os ciclos são controlados através de algumas condições que fazem com que alguns nós ignorem mensagens de outros. Mas obrigado por teres mencionado esse facto senão esquecíamos-nos dos ciclos e aquilo ficava uma grande embrulhada. Próximo desafio é a mediana dos nós. Ainda estamos a pensar nisso. Mais uma vez obrigado pelas dicas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como não respondeste pensei que o problema estava resolvido.

Independentemente de como o resolveram, eu resolveria da seguinte forma (a média): aplicaria algo como o algoritmo de Tarjan para encontrar as componentes fortemente conexas, juntando todos os nós que pertençam a um ciclo num super nó, cujo valor seria a média de todos (teria ainda um valor adicional para saber o seu peso).

Depois de remover os ciclos, ficaria com uma árvore simples, e a média passaria a ponderada considerando os pesos de cada nó.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora