Abbildung 1: Netzwerk mit Uhrzeiten. Mit Ausnahme der durch eine gestrichelte Linie verbundenen Knoten liegen Uhrzeiten von benachbarten Knoten um höchstens eine Minute auseinander. Unser Ziel ist, die Uhrzeiten benachbarter Knoten möglichst nah beieinander zu halten.

Nachbarschaftssynchronisation ist eine Variante des generellen Uhrensynchronisationsproblems, bei der es darum geht, in einem Netzwerk von Computern eine gute Synchronisation zwischen  „benachbarten“ Computern zu erreichen, d.h. solchen, die direkt miteinander kommunizieren können. Als ein konkretes Beispiel stelle man sich ein Netzwerk vor, das aus Dörfern besteht. Jedes Dorf teilt seiner Umgebung die lokale Zeit durch Läuten der Kirchenglocken mit, was in benachbarten Dörfern zu hören ist. Das Ziel ist nun, dass die Dörfer ihre Kirchenuhren so stellen, dass die benachbarten Dörfer – also die in Hörreichweite – so genau wie möglich die gleiche Zeit haben. Obwohl nur Synchronisation zwischen unmittelbaren Nachbardörfern gefordert ist, hat dieses Problem hat die überraschende Eigenschaft, dass die bestmögliche Synchronisationsgarantie davon abhängt, wie groß das Netzwerk insgesamt ist. Wenn man nur die Dörfer in Deutschland synchronisieren will, geht das besser als wenn man das gleiche für ganz Europa versucht! Das ist auf den ersten Blick keineswegs selbstverständlich, weil man erwarten kann, dass eine große Zeitdifferenz zu beispielsweise Portugal gleichmäßig auf der Strecke über Spanien und Frankreich bis nach Deutschland verteilt werden kann.

Aus der Theorie ist ein optimaler Algorithmus für diese Aufgabe seit 10 Jahren bekannt, aber es verbleiben noch viele Fragen zu Verallgemeinerungen und praktischer Implementierung offen. Beispielsweise wurde gezeigt, dass der Algorithmus auf dynamische Netzwerke, d.h. solche, die sich mit der Zeit verändern, angepasst werden kann. Kürzlich hat unsere Arbeitsgruppe gezeigt, dass der Algorithmus ebenfalls so modifiziert werden kann, dass er in Netzwerken funktioniert, in denen ein Teil der Knoten aktiv versucht, den Algorithmus und damit die Synchronisation zu stören.

Um die theoretischen Vorzüge des Algorithmus praktisch nutzbar zu machen, arbeitet unsere Arbeitsgruppe an Implementierungen. Konkret bedeutet das, dass wir Schaltkreise entwickeln, die den Algorithmus möglichst robust gegenüber den inhärenten Ungenauigkeiten zu implementieren, die sich aus den physikalischen Beschränkungen der zu Grunde liegenden technischen Realisation ergeben. Kürzlich haben wir bereits eine Implementierung für ein einfaches System aus nur zwei Knoten entwickelt. Wir arbeiten gegenwärtig daran, diesen Ansatz auf beliebige Netzwerke zu verallgemeinern. Eine solche Implementierung wird dann als Grundlage für die Entwicklung von high-performance Systemen und Computernetzwerken dienen.