El problema del chisme en los sistemas distribuidos es el siguiente. Tenemos un gráfico con n vértices. Cada vértice v tiene un mensaje m v que debe enviarse a todos los nodos.
Ahora, mi pregunta está en el contexto del modelo de red ad-hoc (suponemos que un nodo no tiene ningún conocimiento previo sobre la topología de la red, sus grados de entrada y salida, y el conjunto de sus vecinos. De hecho, el solo el conocimiento de cada nodo es su propio identificador y el número total de nodos).
También supongo que todos los nodos tienen acceso a un reloj global y funcionan sincrónicamente en pasos de tiempo discretos llamados rondas.
La complejidad de un algoritmo en este contexto es el número de rondas necesarias para completar.
Recuerdo que existe un algoritmo que resuelve el problema de cotilleo en rondas con alta probabilidad. Pero ya no puedo encontrar la referencia, y me pregunto si hay resultados más recientes al respecto.
edite siguiendo el comentario juicioso: en cada ronda, un nodo puede transmitir el mensaje a todos sus vecinos y puede recibir los mensajes de ellos. Un nodo recibirá un mensaje en una ronda determinada si y solo si uno de sus vecinos transmite exactamente en esa ronda. De lo contrario, se produce una colisión y el nodo no recibe ninguno de los mensajes.
fuente
Respuestas:
Creo que la referencia que está buscando es el documento "Algoritmos de transmisión en redes de radio con topología desconocida" por Czumaj y Rytter. Parece que este documento hace algunas mejoras, pero creo que depende de los detalles del modelo.
fuente
Editar: no importa, esto no funciona. En el gráfico completo, todos los nodos terminarían retransmitiendo principalmente los mismos mensajes populares y muchos mensajes nunca serían recibidos por ningún nodo que no sea la fuente. ¿Quizás ayudaría si los nodos prefieren transmitir mensajes que han recibido con menos frecuencia?
fuente