Clock Synchronization Flashcards
Wie ist die Duration definiert?
Duration bezeichnet eine Sektion der Timeline
Hat ein Event eine Duration?
Nein, weil ein Event zu einem Zeitpunkt geschieht
Wie ist causality definiert?
Wenn Event e1 eine Ursache für Event e2 ist, dann ist eine kleiner Variation in e1 mit einer kleinen Variation in e2 verbunden, während der umgekehrte Fall nicht unbedingt gilt
Was ist bzw. verursacht einen alarm shower?
Ein alarm shower wird durch ein primary alarm event ausgelöst, welches einen shower aus secondary alarm events auslöst
Kann das primary alarm event identifiziert werden?
Wenn die (teilweise) zeitliche Reihenfolge zwischen alarm events festgestellt wurde, ist es möglich, ein alarm event, das definitiv später als andere alarm events auftrat, als primäres event auszuschließen
Was ist eine Clock?
Eine Uhr ist ein Gerät, das einen Zähler enthält und diesen Zähler in regelmäßigen Abständen (Microticks) erhöht
Wie ist die Granularität einer Clock definiert?
Granularität einer Uhr ist die Anzahl von Microticks der Referenzuhr zwischen zwei beliebigen aufeinanderfolgenden Microticks der Uhr
Was ist ein Timestamp?
Bei einer Uhr und einem Event ist ein Timestamp des Events der Zustand der Uhr unmittelbar nach dem Auftreten des Events, bezeichnet mit clock(event)
Was ist Clock Drift?
Der Begriff bezieht sich auf mehrere miteinander zusammenhängende Phänomene, bei denen eine Uhr nicht genau mit der gleichen Geschwindigkeit läuft wie eine Referenzuhr
Welche Driftrate hat eine perfekte Uhr?
Eine perfekte Uhr hat eine Driftrate von 0
Welche Driftrate hat eine echte Uhr?
Driftraten von 10^-2 bis 10^-8
Was ist precision?
Precision ist der Versatz zwischen zwei Uhren bei einem Tick
Was ist internal synchronization?
Internal Synchronization ist der Prozess der gegenseitigen Resynchronisation eines Ensembles von Uhren zur Aufrechterhaltung einer begrenzten Genauigkeit
Was ist accuracy?
Die Genauigkeit gibt die maximale Abweichung einer bestimmten Uhr von der Zeitreferenz an
Was ist external synchronisation?
External synchronisation ist der Prozess der Resynchronisation einer Uhr mit der Referenzuhr
Welche time standards gibt es?
- International Atomic Time (TAI)
- Universal Time Coordinated (UTC)
Was ist Global Time und wozu dient sie?
- Wenn eine einzige Referenzuhr zur Verfügung steht, können alle Zeitmessungen mit dieser einen Uhr durchgeführt werden, diese dient dann als global time
- Synchronisation der Uhren, um eine gemeinsame Zeitvorstellung zu erreichen
Was wenn es keine global time-base gibt?
Es gibt n unabhängige lokale Zeitreferenzen, und die Zeitstempel können nur in Beziehung gesetzt werden, wenn sie von der gleichen Uhr stammen
Was sind Vorraussetzungen für eine global time base?
- Chronoscopic behavior, keine Diskontinuitäten, auch an Resynchronisationspunkten nicht
- Bekannte precision
- Hohe Verlässlichkeit
- Metrik einer physikalischen Sekunde
Wann ist eine global time reasonable?
Eine globale Zeit wird als angemessen bezeichnet, wenn alle lokalen Implementierungen der globalen Zeit die resonableness condition erfüllen
Wie lautet die reasonableness condition (Angemessenheitsbedingung)?
Für die globale Granularität g eines Macroticks gilt g > PI
Wozu dient die reasonableness condition?
Die Angemessenheitsbedingung stellt sicher, dass der Synchronisationsfehler auf weniger als ein Makrogranulum, d.h. die Dauer zwischen zwei Macroticks, begrenzt ist
Was meint ein Tick Unterschied?
Wegen der Akkumulation des Synchronisationsfehlers und des Digitalisierungsfehlers ist es nicht möglich, die zeitliche Reihenfolge zweier Events zu rekonstruieren mit dem Wissen, dass die globalen Zeitstempel um eins abweichen
Wann ist eine timebase dense?
Eine timebase ist dense, wenn Events an jedem beliebigen Punkt der timeline auftreten können
Was sind Konsequenzen der Grenzen der Zeitmessung?
- Wenn ein einzelnes Event, das auf einer dense timebase auftritt, von zwei Nodes des verteilten Systems beobachtet wird, dann ist ein explizites Protokoll erforderlich, um eine konsistente Sicht des Zeitpunktes des Auftretens von Events zu schaffen
- Wenn zwei Ereignisse auf einer dense timebase auftreten, ist es unmöglich, die zeitliche Reihenfolge der Events immer wiederherzustellen, wenn sie innerhalb eines Intervalls von 3g auftreten
Was ist eine sparse timebase?
Wenn das Auftreten von Events auf einige aktive Intervalle mit einer Dauer PI und einem Ruheintervall Delta zwischen zwei aktiven Intervallen beschränkt ist
Wie wird der verteilte Zustand einer sparse timebase konsistent gemacht?
- Interval of silence mit klar definierten distributed state des Systems
- Interval of activity mit Kommunikations- und Berechnungsaktivität
Was sind Malicious (Byzantine) Clocks?
- Wenn bei drei Clocks eine Clock (absichtlich) falsch geht und den anderen Clocks jeweils eine andere Zeit vermittelt, kann nicht ermittelt werden, welche der Clocks falsch geht
- Anzahl der Clock muss größer gleich (3k+1) sein, dabei entspricht k der Anzahl der malicious Faults
Wie funktioniert der Central Master Algorithm?
- Central Master sendet periodisch seinen Zeitzähler an die Slave Knoten
- Sobald Slave Nachricht erhält, speichert er den Stand seines lokalen Zeitzählers als Eingang der Nachricht
- Differenz zwischen zwischen Zeit in Synchronisationsnachricht und Ankunftszeit beim Slave, korrigiert um die Latenzzeit zum Senden, ist das Maß für die Abweichung zwischen den Uhren
- Slave korrigiert seine Uhr um diese Abweichung
In welche drei Phasen läuft die Synchronisation von distributed clocks typischerweise ab?
- Jeder Knoten wird über globalen Zeitzähler in allen anderen Knoten mit Nachrichten informiert
- Jeder Knoten analysiert gesammelte Informationen und führt Berechnung für Korrektur des lokalen Zeitzählers durch
- Anpassung des lokalen Zeitzählers durch errechneten Korrekturwert
Worin unterscheiden sich Algorithmen zur Resynchronisation von distributed clocks?
- Wie sie die Zeitwerte von den anderen Knoten sammeln
- In der Art der verwendeten Konvergenzfunktion
- Wie der Korrekturwert auf den Zähler angewendet wird
Welche Konvergenzfunktionen gibt es?
- Average Algorithm
- Fault-Tolerant Average (FTA)
- Fault-Tolerant Midpoint
- Interactive Consistency Algorithms
Wie funktioniert der Fault-Tolerant Algorithm?
Jeder Knoten misst die Zeitunterschiede seiner eigenen Uhr und allen anderen Uhren uns sortiert k extreme Differenzen aus, wobei k die Anzahl der byzantinischen Fehler ist, die toleriert werden sollen
Wie funktioniert der Fault-Tolerant Average Algorithm?
Das schlimmste Szenario tritt ein, wenn die byzantinische Uhr ihre (fehlerhaften) Zeitwerte an verschiedene Knotenpunkte in einer anderen Ecke des Systems setzt
Wie funktioniert der Fault-Tolerant Midpoint Algorithm?
- Gemessene Werte sind nach Größe sortiert
- Die k größten und kleinsten Werte werden entfernt
- Auswählen kleinster und größter Wert der verbleibenden Werte
- Addition dieser beiden Werte und teilen durch 2
Was ist State Correction?
- Der von der Konvergenzfunktion berechnete Korrekturwert wird sofort angewendet
- Einfache Anwendung
Was ist der Nachteil der State Correction?
Erzeugung einer Diskontinuität in der Zeitbasis (z.B. wenn die Uhren rückwärts gestellt und derselbe Zeitsollwert zweimal erreicht wird)
Was ist Rate Correction?
- Ändern der Taktrate, um sie während des nächsten Resynchronisationsintervalls zu verlangsamen/beschleunigen
- Ändern der Anzahl der Microticks in einigen Marcroticks
- Durchschnitt der Ratenkorrekturwerte aller Uhren sollte nahe bei Null liegen, um einen Gleichtaktdrift zu vermeiden
Wie funktionieren Interactive Consistency Algorithms?
- Jeder Knoten sendet seine Ansicht des Ensembles an alle anderen Knoten, sodass jeder Knoten die globale Sicht der Situation hat
- Jeder Knoten nimmt diese konsistente Gesamtansicht, d.h. die Matrix der Zeitvektoren, als Grundlage für die Berechnung des Korrekturfaktors
Was ist der Vorteil von Interactive Consistency Algorithms?
Byzantischer Error Faktor gleich 1
Was ist der Nachteil von Interactive Consistency Algorithms?
Zusätzliche Kommunikation
Was ist das Limit der Internal Clock Synchronization?
- In einem System mit n Uhren und einem Delay Jitter epsilon ist es unmöglich, die Uhren besser zu synchronisieren als epsilon(1-(1/n))
Was sind kritische Parameter, die die Qualität der Global Time Base bestimmen?
- Drift offset
- Delay Jitter, am geringsten, wenn die Clock Synchronization sehr nahe an der physikalischen ebene erfolgt
- Auftreten byzantischer Failures ist ein seltenes Event
- Verglichen mit dem Delay Jitter sind algorithmische Effekte gering
Was sind Qualitäts-Attribute einer Global Time Base?
- Precision
- Accuracy
- Fault-Tolerance
- Blackout-Survivability
Was ist Blackout-Survivability?
Blackout Dauer, die toleriert wird, ohne Synchronisation zu verlieren
