文档介绍：Distributed Systems
Principles and Paradigms
Maarten van Steen
VU Amsterdam, Dept. Computer Science
somewhere in it ⇒ we still have to distribute its time to each machine.
Basic principle
Every machine has a timer that generates an interrupt H times per
second.
There is a clock in machine p that ticks on each timer interrupt.
Denote the value of that clock by Cp(t), where t is UTC time.
Ideally, we have that for each machine p, Cp(t) = t, or, in other
words, dC/dt = 1.
5 / 39Distributed Algorithms Clock Synchronization
Physical clocks
dC
> 1
dt dC
Clock time, C = 1
dt
dC
< 1
Fast clock dt
Perfect clock
Slow clock
UTC, t
dC
In practice: 1 − ρ ≤ dt ≤ 1 + ρ.
Goal
Never let two clocks in any system differ by more than δ time units ⇒
synchronize at least every δ/(2ρ) seconds.
6 / 39Distributed Algorithms Clock Synchronization
Global positioning system
Basic idea
You can get an accurate account of time as a side-effect of GPS.
Height
Point to be
ignored
(14,14)
r = 16
(-6,6)
x
r = 10
7 / 39Distributed Algorithms