O problema da fofoca em sistemas distribuídos é o seguinte. Temos um gráfico com n vértices. Cada vértice v possui uma mensagem m v que deve ser enviada para todos os nós.
Agora, minha pergunta está no contexto do modelo de rede ad-hoc (supomos que um nó não tenha nenhum conhecimento prévio sobre a topologia da rede, seus graus de entrada e saída e o conjunto de seus vizinhos. somente o conhecimento de cada nó é seu próprio identificador e o número total de nós).
Suponho também que todos os nós tenham acesso a um relógio global e trabalhem de forma síncrona em intervalos de tempo discretos chamados rounds.
A complexidade de um algoritmo nesse contexto é o número de rodadas necessárias para a conclusão.
Lembro-me de que existe um algoritmo que resolve o problema das fofocas nas rodadas com alta probabilidade. Mas não consigo mais encontrar a referência e estou me perguntando se há resultados mais recentes sobre esse assunto.
edite após o comentário criterioso: a cada rodada, um nó pode transmitir a mensagem a todos os seus vizinhos e pode receber as mensagens deles. Um nó receberá uma mensagem em uma determinada rodada se e somente se exatamente um de seus vizinhos transmitir nessa rodada. Caso contrário, ocorre uma colisão e nenhuma das mensagens é recebida pelo nó.
fonte
Respostas:
Eu acho que a referência que você está procurando é o artigo "Algoritmos de transmissão em redes de rádio com topologia desconhecida", de Czumaj e Rytter. Parece que este artigo faz algumas melhorias, mas acho que depende das especificidades do modelo.
fonte
Edit: não importa, isso não funciona. No gráfico completo, todos os nós acabariam retransmitindo as mesmas mensagens populares e muitas mensagens nunca seriam recebidas por outro nó que não a origem. Talvez ajude se os nós preferirem transmitir mensagens que receberam com menos frequência?
fonte