Mo­no­ton er­­reich­ba­rer De­lau­n­ay­­graph

In diesem Vortrag präsentiere ich das Monotonous-Delaunay-Protokoll, einen lokalen, selbststabilisierenden Algorithmus zur Konstruktion des Delaunaygraphen in verteilten Systemen, der zusätzlich monotone Erreichbarkeit für Broadcast-Operationen garantiert. Das Protokoll ersetzt die bislang gierige Weiterleitung durch eine doppelte sichere Weiterleitung: Knoten leiten Referenzen an je zwei lokale Delaunaynachbarn weiter und schließen die Weiterleitung erst ab, wenn beide Nachbarn durch Acknowledgements bestätigt haben. Dieses Verfahren stellt sicher, dass einmal erreichte Knoten bei identischen zukünftigen Broadcasts ebenfalls erreicht werden. Ich skizziere, warum mit dem Protokoll jede zusammenhängende Starttopologie zu einem Delaunaygraphen konvergiert; die obere Worst-Case-Schranke für die Konvergenz beträgt O(n³) Runden (mit einer Verbesserung auf O(n), falls die Anfangstopologie bereits einen Delaunaygraphen enthält). Zudem sind die Kosten für dynamische Änderungen wie das Hinzufügen und Entfernen von Knoten lokal begrenzt. Wichtige technische Elemente sind das ackBuffer-Konzept und Mechanismen zur Vermeidung von Deadlocks und doppelten Nachrichten. Damit stellt das Monotonous-Delaunay-Protokoll eine Lösung dar, die formale Korrektheit und robuste, verteilte Broadcasts vereint und durch ihr anwendungsnahes Design eine einfache praktische Implementierung ermöglicht.