Gossiping

Em sistemas distribuídos um protocolo de propagação de boatos, ou gossiping simplesmente, é uma categoria de protocolo de comunicação que propaga informação de forma análoga a propagação de um boato em um dado círculo social. Este tipo de protocolo também é chamado muitas vezes de propagação epidêmica que, essencialmente, é igual à propagação de boatos.

Visão Geral

Protocolos baseados em boatos são utilizados para propagar informação local de forma eficiente e escalável. Neste tipo de protocolo não existe nenhuma entidade centralizada responsável por coordenar a troca de mensagens e a única restrição é que a atualização de uma dada informação deve ser gerada em um único nó. Note que a inserção de uma nova informação pode ser considerada como uma atualização da mesma.

Podemos ilustrar o funcionamento de tal protocolo usando a propagação de um boato num dado círculo social:

• Antônio tem uma nova notícia da qual ele quer compartilhar com seus colegas de escritório;
• Antônio então encontra-se com André e conta a boa nova;
• André, ao saber da notícia, resolve ligar para o ramal de Beto para contar a novidade.

Assumindo que, cada pessoa ao saber da notícia irá comportar-se da mesma forma, logo a notícia terá se espalhado por todas as pessoas do escritório.

Diferente do flooding cada nó propaga uma atualização para um número pequeno de nós, em geral, escolhido de forma aleatória. A escolha aleatória de para qual nó a atualização será propagada garante a este tipo de protocolo uma característica probabilística. Pode-se imaginar que é necessário conhecer todos os nós do sistema para que seja possível selecionar aleatoriamente um nó a fim de propagar uma atualização, entretanto não há tal necessidade se for mantida uma visão parcial, atualizada periodicamente, do sistema. A manutenção desta visão manterá os nós organizados em um grafo aleatório, o que garante as propriedades necessárias para a seleção aleatória.

De maneira geral, se definirmos uma rodada como um período em que cada nó do sistema tentará propagar uma atualização para no mínimo um outro nó, o número de rodadas necessárias para que propagar uma atualização é O(log(N)), onde N é o número de nós no sistema. Temos assim que o esta prática é escalável.

Propagação epidêmica

A propagação epidêmica é baseada na forma sobre a qual doenças infeciosas se propagam, e o seu uso, diferente do que apontam as organizações de saúde, visa infectar o maior número de nós possíveis.

Para continuarmos, definiremos um nó como infectado se ele já possuir a versão mais atual da informação que esta sendo propagada, e como suscetível, caso contrário.

O modelo mais conhecido de propagação epidêmica é o modelo da antientropia. Neste modelo, como já dito anteriormente, um dado no A escolhe aleatoriamente um nó B e então A e B trocam informações. Esta troca, entretanto, pode se dá de três diferentes formas:

• push/empurre: A envia para B uma atualização;
• pull/puxe: A solicita à B uma atualização;
• push and pull/empurre e puxe: A envia à B uma atualização e espera que o mesmo retorne-o uma outra atualização, caso haja.

Se considerarmos um sistema no qual muitos nós estão infectados, a utilização da abordagem empurre pode ser uma má idéia, uma vez que a probabilidade de um nó infectado selecionar um nó suscetível é relativamente pequena. Neste cenário a utilização da abordagem puxe funciona muito melhor e os nós suscetíveis serão os responsáveis pela propagação da informação. Contudo, é sabido que a utilização da abordagem empurre e puxe é a melhor estratégia.

Tipicamente, ao se utilizar um protocolo baseado em propagação epidêmica a aplicação irá periodicamente propagar uma atualização (ou um conjunto das mesmas). Desta forma é possível garantir que a informação será mantida consistente em todo o sistema, independente da entrada e saída de nós, desde que exista sempre pelo menos um nó ativo no sistema. Note que um nó pode escolher em qualquer momento um nó já infectado ou ainda que não haja nós suscetíveis no sistema, entretanto cada nó continuará a tentar infectar um outro nó.

Gossiping

Na propagação de boato, diferentemente da propagação epidêmica, é a geração/recebimento de uma atualização que dispara o mecanismo de propagação. Assim, não há mais rodadas fixas nas quais cada nó realiza a propagação, ao invés disso cada nó, ao receber uma atualização escolhe um outro nó aleatoriamente e propaga a atualização. Para aumentar a eficiência, uma vez que um nó tenha recebido uma atualização ele pode passar a propagar a mesma periodicamente.

Entretanto, no gossiping, caso um nó tente propagar uma determinada atualização para um outro nó e este outro nó já tiver recebido a atualização em questão, o nó propagador perde o interesse em propagar aquela nova informação. Este mecanismo é análogo à vida real. André não terá mais interesse em propagar a informação recebida de Antônio caso descubra que essa informação não é mais novidade.

Desta forma, embora gossiping seja uma forma eficiente de propagar uma nova informação na rede, não é possível garantir que todos os nós serão atualizados.

Remoção de Dados

Embora protocolos baseados em propagação de boatos sejam extremamente eficientes para propagar informação, é difícil remover um dado do sistema. Isso acontece porque se simplesmente removermos o dado de um determinado nó, o dado pode ser novamente propagado por um outro nó que ainda não teve o dado removido.

Há, contudo, algumas alternativas para contornar tal problema:

Uma primeira abordagem é determinar o tempo de vida de cada informação, sendo a mesma excluída após este tempo de vida. Porém, esta abordagem exige que a informação seja republicada após o seu tempo de vida caso deseje-se que a mesma permaneça viva por um período maior.

Outra possível abordagem é cada atualização possuir um número de versão. de forma que para remover um item envia-se uma nova atualização de remoção de conteúdo, que chamaremos de certificado de óbito, com um número de versão maior que a última atualização. O problema desta solução é que com o tempo cada nó irá acumular um grande número de certificados de óbito. Para contornar tal problema pode-se adotar a primeira abordagem para os certificados de óbito, ou seja, determinar um tempo de vida para os certificados de óbito. Novamente o problema aqui é determinar qual o tempo médio de propagação da informação.

Dependendo da natureza da informação que seu sistema irá propagar é possível utilizar uma abordagem híbrida, tal como ilustrada a seguir:

Exemplo

O bigoo é um sistema de alocação de caronas peer-to-peer que utiliza um protocolo baseado em propagação epidêmica para propagar as caronas.

Neste sistema as caronas possuem um número de versão, um número finito de vagas e uma data na qual a carona irá ocorrer. Cada nó remove de forma automática uma carona uma vez que a mesma já tenha ocorrido. Entretanto em determinadas situações pode ser necessário remover uma carona do sistema, por exemplo, caso a pessoa que esteja oferecendo a carona desiste de oferecer a mesma, ou caso a as vagas tenham esgotado simplesmente.

Nestes casos é propagada uma nova atualização da carona com o número de vagas igual a 0. Note que embora esta carona esteja 'inválida', já que nenhum nó mais pode requisitá-la, ela permanecerá no sistema até a sua data de expiração.

Referências gerais

• Tanenbaum, A.S.; Steen, M.V. 2002. Distributed Systems - Principles and Paradigms. Prentice Hall.
• Bigoo