Le problème des commérages dans les systèmes distribués est le suivant. Nous avons un graphe avec n sommets. Chaque sommet v a un message m v qui doit être envoyé à tous les nœuds.
Maintenant, ma question se situe dans le contexte du modèle de réseau ad hoc (nous supposons qu'un nœud n'a aucune connaissance préalable de la topologie du réseau, de ses degrés d'entrée et de sortie et de l'ensemble de ses voisins. En fait, le seule la connaissance de chaque nœud est son propre identifiant et le nombre total de nœuds).
Je suppose également que tous les nœuds ont accès à une horloge globale et fonctionnent de manière synchrone par pas de temps discrets appelés tours.
La complexité d'un algorithme dans ce contexte est le nombre de tours nécessaires pour l'achèvement.
Je me souviens qu'il existe un algorithme qui résout le problème des commérages dans les rondes avec une forte probabilité. Mais je ne trouve plus la référence, et je me demande s'il y a des résultats plus récents à ce sujet.
éditer suivant le commentaire judicieux: à chaque tour un nœud peut transmettre le message à tous ses voisins et peut en recevoir les messages. Un nœud recevra un message à un tour donné si et seulement si exactement un de ses voisins transmet à ce tour. Sinon, une collision se produit et aucun des messages n'est reçu par le nœud.
la source
Réponses:
Je pense que la référence que vous recherchez est l' article "Algorithmes de diffusion dans les réseaux radio avec une topologie inconnue" de Czumaj et Rytter. Il semble que ce document apporte quelques améliorations, mais je pense que cela dépend des spécificités du modèle.
la source
Edit: tant pis, cela ne fonctionne pas. Sur le graphique complet, tous les nœuds finiraient par retransmettre principalement les mêmes messages populaires et de nombreux messages ne seraient jamais reçus par un nœud autre que la source. Peut-être que cela aiderait si les nœuds préfèrent transmettre des messages qu'ils ont reçus moins fréquemment?
la source