Berkeley-Algorithmus

Der Berkeley-Algorithmus dient der Synchronisation von logischen Uhren in verteilten Systemen. Er sorgt also nicht für eine global gültige Zeit, sondern nur für eine temporale Ordnung von Ereignissen (die sogenannte Kausale Ordnung). Er erfordert eine zentrale Komponente, den sogenannten Zeitdaemon.

Ablauf

Jeder Rechner wird in regelmäßige Abständen nach seiner Zeit gefragt. Aus den erhaltenen Antworten errechnet der Zeitdaemon den Mittelwert der empfangenen Zeiten und teilt den Rechnern im Netz die jeweilige zeitliche Differenz ihrer Uhren mit. Die Rechner müssen dann ihre Uhren im Falle einer positiven Differenz auf den aktuellen Wert stellen oder im Falle einer negativen Differenz ihre Uhren verlangsamen - um die kausale Ordnung der Ereignisse aufrechtzuerhalten, dürfen sie ihre Uhren nicht zurückstellen.

Mögliche Mittelwertalgorithmen

Der Mittelwert der empfangenen Zeiten kann nach verschiedenen Vorgehensweisen errechnet werden:

• Errechnen des arithmetischen Mittels (also des Durchschnitts aller Werte)
• Streichen der höchsten und tiefsten Extremwerte und Errechnen des arithmetischen Mittels
• Gewichtung jeder empfangenen Zeit mit einem Erwartungswert und Errechnen des gewichteten arithmetischen Mittels. Der Erwartungswert kann aus der Netzwerktopologie gefolgert werden.

Referenzen

Vorlesung Verteilte Systeme/Ubiquitous Computing der Ludwig-Maximilians-Universität München im SS06