Das Klatschproblem in verteilten Systemen ist das folgende. Wir haben einen Graphen mit n Ecken. Jeder Vertex v hat eine Nachricht m v , die an alle Knoten gesendet werden muss.
Meine Frage bezieht sich nun auf das Ad - hoc - Netzwerkmodell (wir gehen davon aus, dass ein Knoten keine Vorkenntnisse über die Topologie des Netzwerks, seine In - und Out - Grade und die Menge seiner Nachbarn hat Nur die Kenntnis jedes Knotens ist seine eigene Kennung und die Gesamtzahl der Knoten.
Ich gehe auch davon aus, dass alle Knoten Zugriff auf eine globale Uhr haben und synchron in diskreten Zeitschritten arbeiten, die als Runden bezeichnet werden.
Die Komplexität eines Algorithmus ist in diesem Zusammenhang die Anzahl der Runden, die zur Vervollständigung benötigt werden.
Ich erinnere mich, dass es einen Algorithmus gibt, der das Klatschproblem in Runden mit hoher Wahrscheinlichkeit löst . Aber ich kann den Verweis nicht mehr finden und frage mich, ob es zu diesem Thema neuere Ergebnisse gibt.
Bearbeiten Sie nach dem vernünftigen Kommentar: In jeder Runde kann ein Knoten die Nachricht an alle seine Nachbarn senden und die Nachrichten von ihnen empfangen. Ein Knoten erhält eine Nachricht in einer bestimmten Runde, wenn genau einer seiner Nachbarn in dieser Runde sendet. Andernfalls tritt eine Kollision auf und keine der Nachrichten wird vom Knoten empfangen.
quelle
Antworten:
Ich denke , die Referenz Sie suchen , das ist Papier „Rundfunk - Algorithmen in Funknetzen mit unbekannter Topologie“ von Czumaj und Rytter. Es scheint, dass dieses Papier einige Verbesserungen bringt, aber ich denke, dass es von den Besonderheiten des Modells abhängt.
quelle
Bearbeiten: egal, das funktioniert nicht. In der vollständigen Grafik würden alle Knoten zumeist die gleichen populären Nachrichten erneut senden, und viele Nachrichten würden niemals von einem anderen Knoten als der Quelle empfangen werden. Vielleicht hilft es, wenn die Knoten Nachrichten senden möchten, die sie seltener empfangen haben?
quelle