DISTRIBUTED SYSTEMS Principles and Paradigms Second Edition ANDREW S. TANENBAUM MAARTEN VAN STEEN Chapter 6 Synchronization
DISTRIBUTED SYSTEMS Principles and Paradigms Second Edition ANDREW S. TANENBAUM MAARTEN VAN STEEN Chapter 6 Synchronization
Clock Synchronization
Figure 6-1. When each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time.
Physical Clocks (1)
Figure 6-2. Computation of the mean solar day.
Physical Clocks (2)
Figure 6-3. TAI seconds are of constant length, unlike solar seconds. Leap seconds are introduced when necessary to keep in phase with the sun.
Global Positioning System (1)
Figure 6-4. Computing a position in a two-dimensional space.
Global Positioning System (2)
Real world facts that complicate GPS
It takes a while before data on a satellite’s position reaches the receiver.
The receiver’s clock is generally not in synch with that of a satellite.
Clock Synchronization Algorithms
Figure 6-5. The relation between clock time and UTC when clocks tick at different rates.
Figure 6-6. Getting the current time from a time server.
NTP
ntpd
si possono configurare più server NTP di riferimento in /etc/ntpd.conf.
ntpd stima l'errore sistematico, e lo corregge.
Es. da shell:
ntpdate ntp1.inrim.it
The Berkeley Algorithm (1)
Figure 6-7. (a) The time
daemon asks all the other
machines for their clock
values.
The Berkeley Algorithm (2)
Figure 6-7.
(b) The machines answer.
The Berkeley Algorithm (3)
Figure 6-7. (c) The time
daemon tells everyone how
to adjust their clock.
Reference Broadcast Synchronization (RBS)
Ha lo scopo di sincronizzare i clock tra di loro piuttosto che impostarli con precisione con un clock di riferimento esterno (es. reale);
Un nodo invia il tempo di riferimento con un broadcast;
Gli altri si adeguano.
Clock Synchronization in Wireless Networks (1)
Figure 6-8. (a) The usual
critical path in determining
network delays.
Clock Synchronization in Wireless Networks (2)
Figure 6-8. (b) The
critical path in the
case of RBS.
Lamport’s Logical Clocks (1)
The "happens-before" relation → can be observed directly in two situations:
If a and b are events in the same process, and a occurs before b, then a → b is true.
If a is the event of a message being sent by one process, and b is the event of the message being received by another process, then a → b
Lamport’s Logical Clocks
a and b are concurrent
a → b is false
b → a is false
Lamport’s Logical Clocks
Time value C(a), C(b)
a → b
C(a) < C(b)
Lamport’s Logical Clocks (2)
Figure 6-9. (a) Three processes, each with its own clock. The clocks run at different rates.
Comments