complexidade de fofocas aleatórias

13

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.Gnvmv

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.O(nregistro2n)

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ó.

Sylvain Peyronnet
fonte
3
Eu acho que você está assumindo que em cada rodada cada nó pode enviar uma mensagem para apenas um vizinho? Caso contrário, o problema é trivial para resolver em rounds ...O(n)
Jukka Suomela
Oups, esqueci de mencionar sobre isso, eu editei de acordo.
Sylvain Peyronnet
Se um nó recebeu mensagens m u e m w, ele pode transmitir { m v , m u , m w } em uma única rodada ou as mensagens transmitidas são limitadas ao tamanho de apenas uma carga útil? vmvocêmW{mv,mvocê,mW}
Warren Schudy
Os nós podem dizer a diferença entre uma colisão e ninguém transmitindo?
Warren Schudy 25/10/10
O gráfico de conexões é um gráfico direcionado arbitrariamente fortemente conectado?
Warren Schudy 25/10/10

Respostas:

11

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.

Lev Reyzin
fonte
Sim, este é o jornal que eu estava procurando. Obrigado !
Sylvain Peyronnet
0

t2-(tmodregistron) e escolhe a mensagem para transmitir uniformemente aleatoriamente dentre as mensagens que recebeu até o momento. Isso pode funcionar?

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?

Warren Schudy
fonte