05 - Clock Synchronization

Question 1

Wie ist Duration definiert?

Answer 1

Duration bezeichnet eine Sektion der Time Line.

Question 2

Hat ein Event eine Duration?

Answer 2

Nein, weil ein Event zu einem Zeitpunkt geschieht.

Question 3

Wie ist Causality definiert?

Answer 3

“Wenn Ereignis e1 eine Ursache für Ereignis e2 ist, dann ist eine kleine Variation (eine Markierung) in e1 mit einer kleinen Variation in e2 verbunden, während kleine Variationen in e2 nicht unbedingt mit kleinen Variationen in e1 verbunden sind.”

Question 4

Was ist bzw. verursacht einen Alarm Shower?

Answer 4

Ein Alarm Shower wird durch ein primary alarm event ausgelöst, welches einen shower aus secondary alarm events auslöst.

Question 5

Kann das primary alarm event identifiziert werden?

Answer 5

Wenn die (teilweise) zeitliche Reihenfolge der Alarmereignisse festgestellt wurde, ist es möglich, ein Alarmereignis, das definitiv später als andere Alarmereignisse auftrat, als das primäre Ereignis auszuschließen. Eine präzise global time-base hilft bei der Bestimmung der Ereignis Menge, die sich in
dieser definitiv-späteren Beziehung befindet.

Question 6

Was ist eine Clock?

Answer 6

Eine Uhr ist ein Gerät, das einen Zähler enthält und diesen Zähler in regelmäßigen Abständen (Microticks) erhöht.

Question 7

Wie ist die Granularität einer Clock definiert?

Answer 7

Granularität einer Uhr C ist die Anzahl der Mikroticks der Referenzuhr zwischen zwei beliebigen aufeinanderfolgenden Mikroticks von C.

Question 8

Was ist ein Timestamp?

Answer 8

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).

Question 9

Was ist Clock Drift?

Answer 9

Ist die Abweichung einer lokalen Uhr von der Referenzuhr.

Question 10

Welche Driftrate hat eine Perfect Clock?

Answer 10

Eine Driftrate von 0.

Question 11

Welche Driftrate hat eine Real Clock?

Answer 11

Driftraten von 10^−2 bis 10^−8

.

Question 12

Was ist Precision?

Answer 12

Ist der Versatz zwischen zwei Uhren bei einem Tick.

Question 13

Was ist Internal Synchronization?

Answer 13

Ist der Prozess der gegenseitigen Resynchronisation eines Ensembles von Uhren zur Aufrechterhaltung einer begrenzten Genauigkeit.

Question 14

Was ist Accuracy?

Answer 14

• Der Versatz der Uhr k gegenüber der Referenzuhr Uhr z bei Tick i wird als Genauigkeit bezeichnet.
• Die Genauigkeit gibt die maximale Abweichung einer bestimmten Uhr von der externen Zeitreferenz an.
• wenn alle Uhren extern mit einer Genauigkeit A synchronisiert sind, dann ist das Ensemble auch intern mit einer Genauigkeit von höchstens 2 A synchronisiert. Das Gegenteil ist nicht der Fall.

Question 15

Was ist External Synchronization?

Answer 15

Ist der Prozess der Resynchronisation einer Uhr mit der Referenzuhr.

Question 16

Was ist Global Time und wozu dient sie?

Answer 16

• Wenn eine einzige Referenzuhr zur Verfügung steht, können alle Zeitmessungen mit dieser einen Uhr durchgeführt werden, die als gemeinsame “globale” Zeit dient.
• in einem verteilten System synchronisieren wir die Uhren, um eine gemeinsame Zeitvorstellung, eine “globale Zeit” im verteilten System zu erzeugen.
• eine solche globale Zeit ist jedoch ein abstrakter Begriff, der durch die Uhren in den Knoten nur angenähert werden kann.
• Es ist möglich, eine Teilmenge der Mikroticks jeder lokalen Uhr k für die Erzeugung der lokalen Implementierung eines globalen Begriffs der Zeit auszuwählen. Wir nennen einen solchen ausgewählten lokalen Mikrotick einen Makrotick (oder einen Tick) der globalen Zeit.

Question 17

Was ist wenn es keine Global Time-Base gibt?

Answer 17

• Es gibt n unabhängige lokale Zeitreferenzen, und die Zeitstempel können nur in Beziehung gesetzt werden, wenn sie von der gleichen Uhr stammen.
• Intervallmessungen zwischen Events, die an verschiedenen Knoten beobachtet werden, sind durch den End-to-End-Delay-Jitter begrenzt.
• der Verzögerungsjitter des (ET-)Kommunikationssystems bestimmt den Jitter in den Regelkreisen - dies kann für viele Echtzeitregelungsanwendungen unannehmbar sein.
• State Estimation ist sehr schwierig, da der genaue Zeitpunkt der Messung einer Prozessvariablen nicht bekannt ist.

Question 18

Was sind Anforderungen an eine Globale Time Base? (4)

Answer 18

• Chronoscopic behavior, i.e. no discontinuities, even at the points of resynchronization
• bekannte precision (Known precision)
• hohe Zuverlässigkeit (High dependability)
• Metrik der physikalischen Sekunde (Metric of the physical second)

Question 19

Wozu dient die Reasonableness Condition?

Answer 19

Die Angemessenheitsbedingung stellt sicher, dass der Synchronisationsfehler auf weniger als ein Makrogranulum, d. h. die Dauer zwischen zwei Makroticks, begrenzt ist.

Question 20

Was meint ein Tick Unterschied?

Answer 20

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.

Question 21

Wann ist eine Timebase dense?

Answer 21

Wenn Events an jedem beliebigen Punkt der Timeline auftreten können.

Question 22

Was sind Konsequenzen der Grenzen der Zeitmessung?

Answer 22

• Wenn ein einzelnes Ereignis, das auf einer dense Timebase auftritt, von zwei Nodes des verteilten Systems beobachtet wird (z.B. um eine Redundanz in den Beobachtungen zu erreichen), dann ist ein explizites Protokoll erforderlich, um eine konsistente Sicht des Zeitpunkts 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.

Question 23

Wie wird der verteilte Zustand bei einer Sparse Time Base konsistent gemacht?

Answer 23

• gibt Interval of Silence mit klar definiertem distributed State des Systems
• gibt Interval of activity mit Kommunikations- oder Berechnungsaktivität

Question 24

Was sind Malicious (Byzantine) Clocks?

Answer 24

Wenn bei drei Clocks eine Clock “absichtlich” falsch geht und den anderen Clocks jeweils eine andere Zeit mitteilt, kann nicht ermittelt werden, welche der Clocks falsch geht. Es kann erst wieder bestimmt werden, wenn die Anzahl der Clocks N größer oder gleich 3 ∗ k+1 ist, k ist die Anzahl der malicious (Byzantine) Faults.

Question 25

Wie funktioniert der Central Master Algorithm?

Answer 25

• ein einziger Knoten (central Master) sendet periodisch seinen Zeitzähler in Synchronisationsnachrichten an die Slave-Knoten

• sobald ein Slave einen neuen Zeitwert vom Master erhält, speichert er den Stand seines
lokalen Zeitzählers als Zeitpunkt des Eingangs der Nachricht

• die Differenz zwischen der in der Synchronisationsnachricht enthaltenen Zeit des Masters und der aufgezeichneten Ankunftszeit der Nachricht beim Slave, korrigiert um die Latenzzeit des Nachrichtentransports, ist das Maß für die Abweichung zwischen den Uhren
• der Slave korrigiert seine Uhr um diese Abweichung, um sie mit der Uhr des Masters in Übereinstimmung zu bringen

Question 26

In welchen drei Phasen läuft die Synchronisation von distributed Clocks typischerweise ab?

Answer 26

1. Jeder Knoten erlangt Kenntnis über den Zustand des globalen Zeitzählers in allen anderen Knoten durch den Austausch von Nachrichten zwischen den Knoten.
2. Jeder Knoten analysiert die gesammelten Informationen, um Fehler zu erkennen und führt die Konvergenzfunktion zur Berechnung eines Korrekturwertes für den lokalen globalen Zeitzähler des Knotens durch.
3. Der lokale Zeitzähler des Knotens wird um den berechneten Korrekturwert angepasst.

Question 27

Worin unterscheiden sich Algorithmen zur Resynchronisation von distributed Clocks? (3)

Answer 27

• wie sie die Zeitwerte von den anderen Knoten sammeln
• in der Art der verwendeten Konvergenzfunktion
• wie der Korrekturwert auf den Zeitzähler angewendet wird

Question 28

Welche Konvergenzfunktionen kennen Sie? (4)

Answer 28

• Average Algorithm
• Fault-Tolerant Average (FTA)
• Fault-Tolerant Midpoint
• Interactive Consistency Algorithms

Question 29

Wie funktioniert der Fault-Tolerant Algorithm?

Answer 29

Jeder Knoten misst die Zeitunterschiede zwischen seiner eigenen Uhr und allen anderen
Uhren und sortiert k extreme Differenzen aus, wobei k die Anzahl der byzantinischen Fehler ist, die toleriert werden sollen.

Question 30

Wie funktioniert der Fault Tolerant Average Algorithm?

Answer 30

Das schlimmste Szenario tritt ein, wenn die byzantinische Uhr ihre (fehlerhaften) Zeitwerte an verschiedenen Knotenpunkten in einer anderen Ecke des Systems setzt.

Question 31

Wie funktioniert Fault Tolerant Midpoint?

Answer 31

1. die Messwerte sind nach ihrer Größe geordnet.
2. k größte und k kleinste Werte werden aus dieser Liste gelöscht.
3. der kleinste und der größte Wert werden aus den verbleibenden Werte ausgewählt.
4. diese beiden Werte werden addiert und durch zwei geteilt

Question 32

Was ist State Correction?

Answer 32

• der von der Konvergenzfunktion berechnete Korrekturterm wird sofort angewendet
• einfache Anwendung
• Nachteil: Erzeugung einer Diskontinuität in der Zeitbasis (z. B. wenn die Uhren rückwärts gestellt und derselbe Zeitsollwert zweimal erreicht wird)

Question 33

Was ist Rate Correction?

Answer 33

• Ändern der Taktrate, um sie während des nächsten Resynchronisationsintervalls zu
verlangsamen oder zu beschleunigen

• Ändern der Anzahl der Microticks in einigen Macroticks

• der Durchschnitt der Ratenkorrekturterme aller Uhren sollte nahe bei Null liegen, um
einen Gleichtaktdrift zu vermeiden

Question 34

Wie funktionieren Interactive Consistency Algorithms?

Answer 34

• Um das Problem des byzantinischen Fehlerfaktors zu überwinden, sendet jeder Knoten
seine Ansicht des Ensembles an alle anderen Knoten, sodass jeder Knoten die globale Sicht der Situation hat, d.h. er kann herausfinden, welcher Knoten geschummelt hat.

• Jeder Knoten nimmt diese konsistente Gesamtsicht, d.h. die Matrix der Zeitvektoren,
als Grundlage für die Berechnung des Korrekturfaktors.

• Nachteil: zusätzliche Kommunikation

Question 35

Was sind kritische Parameter, die die Qualität der Global Time Base bestimmen?

Answer 35

• Drift offset
• delay jitter
• auftreten byrantinischer Failures ist ein seltenes Event
• der delay jitter ist am geringsten, wenn die Clock Synchronisation sehr nahe an der physikalischen Ebene erfolgt - durch die Hardware.
• verglichen mit dem delay jitter sind der algorithmische Effekte gering

Question 36

Was sind Qualitäts-Attribute einer Global Time Base? (4)

Answer 36

• Precision: maximale Differenz zwischen den jeweiligen Ticks der Uhren eines Ensembles
• Accuracy: maximale Differenz zwischen dem Tick einer Uhr und dem zugehörigen Tick einer externen Referenzuhr
• Fault-Tolerance: Anzahl und Art der Fehler die das Clocking System tolerieren kann

• Blackout Survivability: Blackout Dauer, die toleriert wird ohne Synchronisation zu
verlieren

Question 37

Was ist Blackout Survivability Interval?

Answer 37

Ist die Blackout-Dauer, die toleriert wird ohne die Synchronisation zu verlieren.