Synchronizing Physical
Clocks
1
Basic Terminologies
1. Time
• The value displayed by a clock at any given moment.
• It represents the current point in a timeline.
Example:
• At a specific moment:
• Ca(t)=10:00:00
• Cb(t)=10:00:05
This indicates that Cb is ahead of Ca by 5 seconds.
The time of a clock in machine p is given by function Cp (t), where Cp (t)=t for
perfect clock.
2
Basic Terminologies
For a perfect clock, Cp(t)=t, meaning:
The clock runs without any error.
It ticks at the exact rate of real-world physical time (no skew or drift).
Its time is always synchronized with the "true" or "absolute" time.
Why is This Important?:
• In distributed systems, perfect clocks are an idealized concept. Real-world clocks often
have imperfections like: Skew, Offset and, Drift.
• Perfect Clock is Theoretical and does not exist in the real world.
Real-World Implications:
• No Clock Is Perfect:
• In reality, Cp(t)≠t for most systems, as all clocks experience offset, skew,
or drift to some extent.
Basic Terminologies
Example:
Perfect Clock: At physical time t=12:00:00 Cp(t)12:00:00.
Imperfect Clock: At physical time t=12:00:00,
If Cp(t)=12:00:05 the clock has an offset of +5 seconds.
4
Basic Terminologies
2. Clock Frequency:
• The rate at which a clock ticks, typically measured in ticks per second (e.g., 1
Hz = 1 tick per second).
• A higher or lower frequency means the clock ticks faster or slower compared
to a reference clock.
• The frequency of clock Ca at time t is: Cꞌa(t).
3. Clock Offset:
• The difference in time values between two clocks at a specific moment.
• OR difference between the time reported by a clock and real time.
• Offset shows how far one clock is ahead or behind another.
5
Basic Terminologies
If Ca (t) is the time reported by a clock a at real time t, then the offset is:
Offset= Ca (t)−t. Where,
Ca (t): Clock time reported by machine a (time reported by a local clock, (e.g., a wristwatch
or a system clock in a
computer).
t: Actual real-world physical time (time as measured by universal time standards, such as
UTC (Coordinated Universal Time) or
GPS time.)
OR Ca (t)− Cb (t).
Example: At t=0, suppose:
• Ca(t)=10:00:00, and Cb(t)=10:00:05
• The offset is 5 seconds, meaning Cb is ahead of Ca by 5 seconds.
6
Basic Terminologies
4. Clock Skew:
• The difference in the rates (frequencies) of two clocks.
• OR difference in the frequencies of the clock and perfect clock.
• It is denoted as: Cꞌa (t)− Cꞌb (t).
5. Clock Drift:
• Local clocks may drift over time due to variations in hardware oscillators. i.e.,
the rate of change of skew over time.
• It is denoted as: Cꞌꞌa (t)− Cꞌꞌb (t).
• Example: One clock may run slightly faster or slower than another.
7
Synchronization of physical clocks
In distributed systems, synchronizing physical clocks across nodes is crucial
for maintaining a consistent view of time.
Since distributed nodes operate independently and have their own local
clocks, discrepancies (like clock skew) can arise due to factors like hardware
differences and network latency.
Synchronizing these clocks is essential for tasks such as ensuring
consistency, event ordering and debugging.
8
Why do clock synchronization?
Synchronizing clocks is critical for ensuring correctness and reliability of time-dependent
operations across multiple machines in distributed environment.
In centralized systems, there is no need for clock synchronization because, generally, there
is only one single clock.
A process gets the time by simply issuing a system call to the kernel.
In distributed systems, there is no global clock or common memory.
Each processor has its own internal clock and its own notion of time.
These clocks can easily drift seconds per day, accumulating significant errors over
time.
Also, because different clocks tick at different rates, they may not remain always
synchronized although they might be synchronized when they start.
This clearly poses serious problems to applications that depend on a synchronized
notion of time.
9
Why do clock synchronization?
Motivation:
For most applications and algorithms that run in a distributed system, we need to
know time in one or more of the following contexts:
The time of the day at which an event happened on a specific machine in the
network.
The time interval between two events that happened on different machines in the
network.
The relative ordering of events that happened on different machines in the network.
Unless the clocks in each machine have a common notion of time, time-based queries
cannot be answered.
10
Why do clock synchronization?
Clock synchronization has a significant effect on many problems like secure systems,
fault diagnosis and recovery, scheduled operations, database systems, and real-world
clock values.
Clock synchronization is the process of ensuring that physically distributed
processors have a common notion of time.
Due to different clocks rates, the clocks at various sites may diverge with time and
periodically a clock synchronization must be performed to correct this clock skew
in distributed systems.
Clocks are synchronized to an accurate real-time standard like UTC (Universal
Coordinated Time).
Clocks that must not only be synchronized with each other but also have to adhere
to physical time are termed physical clocks.
11
Why do clock synchronization?
Time-based computations on multiple machines: Distributed systems often
involve computations that rely on time for coordination and execution.
Examples:
Calculating the time taken for a distributed query to complete across multiple
nodes.
Applications that measure elapsed time: Certain applications require accurate
time measurements to track the duration of processes or operations. Example:
Monitoring system performance or logging events with precise timestamps.
Agreeing on deadlines: tasks that have strict deadlines, all nodes in the system
must have a consistent notion of time. Example: online gaming or financial
transactions
Real time processes may need accurate timestamps: Real-time applications rely
on precise timestamps to execute operations at the correct moment.
12
Why do clock synchronization?
Many applications require similar clocks rates for
Real time scheduling events based on processor clock: Real-time systems schedule tasks
based on processor clock values.
Any deviation between clocks can lead to misaligned task execution. Example:
Scheduling periodic tasks in IoT devices.
Setting timeouts and measuring latencies: Processes require synchronized clocks to
ensure fairness and accuracy.
Without consistent clocks, measuring latencies between nodes is impossible. Example:
Detecting communication delays in distributed message-passing systems.
Ability to infer potential causality from timestamps: Distributed systems often use
timestamps to establish the happens-before relationship between events.
Without synchronized clocks, it becomes impossible to determine the causal order of
events. Example: ensuring the correct sequence of events in distributed logging
13
Example: Gulf War
Iraqi leader Saddam Hussein claimed that Kuwait was historically part of Iraq and accused Kuwait of
overproducing oil, lowering global oil prices, and stealing oil from the Rumaila oil field.
A coalition of 35 countries, led by the United States, was formed under the authorization of the
United Nations to liberate Kuwait.
Iraq launched Scud missiles at coalition forces and civilian targets in Israel and Saudi Arabia.
The U.S. deployed the Patriot Missile Defense System to intercept and destroy these Scud missiles in
mid-flight (in 1990-1991).
While the system was effective in many cases, a critical synchronization error led to failures in
intercepting some missiles.
The Patriot system relied on precise timekeeping to calculate the position of an incoming missile and
launch an interceptor.
The system used an internal clock to track time and perform real-time calculations.
14
Example: Gulf War
Over time, small inaccuracies in the internal clock accumulated, causing the system's clock to "drift" from
the actual time.
After 72 hours of continuous operation, the control system was out of synchronization relative to patriot
guidance system.
When a Scud missile was detected, the Patriot system calculated the expected position of the missile at a
specific time, known as the intercept point.
Due to the clock drift:
The system miscalculated the intercept point, thinking the missile was in a different location than it
actually was.
The interceptor missile was launched but failed to hit the Scud missile, allowing it to strike its target.
On February 25, 1991, a Scud missile hit a U.S. Army barracks in Dhahran, Saudi Arabia, killing 28
soldiers.
The Patriot system failed to intercept the Scud due to a synchronization error caused by clock drift.
15
Physical Clocks
How do we measure real time?
17th century - Mechanical clocks based on astronomical measurements
Solar Day - Transit of the sun (noon to next noon)
Solar Seconds – length of Solar Day/(3600*24) (24 hours and 3600 seconds per our)
Problem (1940) - Rotation of the earth varies (gets slower)
Solution: Mean solar second - average length of a second over many solar days.
By the mid-20th century, atomic clocks replaced astronomical methods because
they are far more stable and precise.
The current definition of a second is based on the vibrations of cesium atoms,
independent of the Earth's rotation.
16
Atomic Clocks
Atomic clocks use the vibrations (transitions) of specific atoms, like Cesium-133, to
measure time with incredible accuracy.
In 1948, it was defined that 9192631779 transitions of Cesium-133 = 1 mean solar
second. (919 crore 26 lakh 31 thousand 779.) 9.19 billion.
TAI - International Atomic Time: The output of atomic clock is called TAI.
TAI provides a steady, highly precise time reference independent of celestial
observations
UTC (Universal Coordinated Time): Coordinated Universal Time (UTC) is an
international time keeping standard based on atomic time but synchronized with Earth's
rotation, with an occasional leap second added or deleted.
17
Atomic Clocks
UTC signals are synchronized and broadcast regularly by various radio stations (Example
WWV in the US broadcasts time signals based on UTC.), satellites (e.g., GEOS, GPS
synchronize their time with atomic clocks to broadcast UTC-based time.).
Signals experience propagation delay due to speed of light, distance from broadcast
source, atmospheric conditions, etc.
Most workstations and PCs don’t have direct UTC receivers.
Instead, computers rely on Network Time Protocol (NTP) servers over the internet to
synchronize their clocks with UTC.
This introduces small inaccuracies due to network delay.
18
Computer clocks
Modern timer chips: Computer clocks use timer chips to keep track of
time.
To maintain synchronized clocks
Can use UTC source (time server) to obtain current notion of time.
Use solutions without UTC:
Ex: Computers synchronize their clocks directly with one another instead of a
central UTC source (peer-to-peer).
Or can use logical clocks or GPS time (which is based on atomic clocks but does
not include leap seconds like UTC).
Ex: GPS receivers in devices like smartphones use GPS time for
synchronization.
19
Clock Synchronization Techniques
There are two main approaches to synchronizing clocks in distributed systems:
External Synchronization
Synchronize all nodes with a reference external clock (e.g., UTC ).
Protocols used are: NTP and PTP
a) NTP (Network Time Protocol):
• One of the most widely used protocols.
• Synchronizes distributed nodes over the network with high accuracy by
communicating with a hierarchy of time servers.
20
Clock Synchronization Techniques
Working of NTP (Network Time Protocol):
Steps:
1.A node sends a request to an NTP server.
2.The server responds with its current time.
3.The node adjusts its clock, accordingly.
b) PTP (Precision Time Protocol):
• Provides higher precision than NTP.
• often used in systems requiring nanosecond accuracy.
• Synchronizes clocks in local area networks (LANs).
PTP synchronizes clocks by exchanging time-stamped messages between a master clock
(reference clock) and slave clocks (devices to be synchronized).
21
Clock Synchronization Techniques
Working of PTP (Precision Time Protocol):
Steps:
1. Send Time: The master clock sends a Sync message to the slave clock with a timestamp
(T1) of when the message was sent.
2. Receive Time: The slave clock records the time (T2) when it receives the Sync message.
3. Delay Request: The slave sends a Delay Request message to the master, recording its
send timestamp (T3).
4. Delay Response: The master responds with a Delay Response message, including the
time (T4) when it received the Delay Request.
5. Slave Calculates Offset and Delay:
Offset: The time difference between its clock and the master clock.
Delay: The time it takes for messages to travel between the master and slave.
22
Clock Synchronization Techniques
Working of PTP (Precision Time Protocol):
Steps:
T4−T1: Total time from when the master sends the Sync message to when the master
receives the Delay Request.
T3−T2: Time spent processing the Delay Request at the slave.
Since the delay is symmetric, divide the Round Trip Time (RTT by) 2.
6. Slave Adjusts Its Clock: The slave clock adjusts its time using the
calculated offset, aligning with the master clock.
23
Clock Synchronization Techniques
Internal Synchronization
Ensure all nodes in the system have clocks synchronized relative to each
other, without referencing an external clock.
Protocols/Algorithms used are:
a) Cristian’s Algorithm:
A designated server is used which periodically sends its time to all nodes in
distributed system.
Steps:
1.A node sends a request to a server.
2.The server responds with its current time.
3.The node adjusts its clock by estimating the round-trip time (RTT)
24
Clock Synchronization Techniques
b) Berkeley’s Algorithm:
A master node polls all other nodes for their local times.
The master averages the times (including its own) and sends adjustments
to all nodes.
Each node adjusts its clock accordingly.
25
Events in Distributed Systems
A distributed program is composed of a set of n asynchronous
processes, p1, p2,………,pn.
The processes do not share a global memory and communicate
solely by passing messages over the network.
The processes do not share a global clock that is instantaneously
accessible to these processes.
Process execution and message transfer are asynchronous.
A process may execute any action spontaneously and a process that
is sending a message doesn’t wait for the delivery of the message.
26
Example:
Let Cij denote the channel from process Pi to process Pj and
let mij denote a message sent by Pi to Pj.
Processes do not share a global clock and process execution and
message transfer is asynchronous.
The message transmission delay is finite and unpredictable.
The global state of this distributed computing is a composition of
the state of processes and the communication channel.
The state of a process is characterized by the state of its local
memory.
27
Events in Distributed Systems
The state of the communication channel is characterized
by the set of messages in the transit.
The execution of a process consists of a sequential
execution of its actions.
The actions are atomic and the actions of a process are
modeled as three types of events namely:
internal events,
message send events, and
message receive events
28
Events in Distributed Systems
Let eix denote the xth event at process pi. (i: process id, x : event
number)(e13: 3rd event of process 1)
For a message m, let send(m) and rec(m) denote its send and receive
events, respectively.
The occurrence of events changes the states of respective processes
and channels.
An internal event changes the state of the process at which it occurs.
A send event changes the state of the process that sends the message
and the state of the channel on which the message is sent.
A receive event changes the state of the process that receives the
message and the state of the channel on which the message is
received.
29
Events in Distributed Systems
An internal event only affects the respective process.
The events at a process are linearly ordered by their order of
occurrence.
is history of Events.
30
Events in Distributed Systems
31
32
33
Example: Causal Precedence Relation
34
Casual Precedence Relation
35
36
36
37
38
38
Logical Clocks
It implements the notion of virtual time.
In a system of logical clocks, every process has a logical
clock that uses a set of rules.
Every event is assigned a timestamp in such a way that
is consistent with the happened-before relationship.
The Causal relationship among different events can be
inferred from their timestamp.
i.e. if an event a causally affects an event b, then the
timestamp of an event a is smaller than the timestamp of
event b.
39
Logical Clocks
A system of logical clocks consists of a time domain t and a logical
clock c.
The logical clock “c” is a function that maps the event “e” in
distributed system to an element in the time domain “T”.
Example:
e → f ⇒ C(e) < C(f) where,
C(e): the timestamp of event e.
C(f): the timestamp of event f.
40
41
42
43
44
45
46
EXAMPLE: TO PRACTICE
t=0
P1
t=0
P2
t=0
P3
47
EXAMPLE: TO PRACTICE
48
49
Scalar Time
Proposed by Lamport in 1978 as an attempt to totally order
events in a distributed system.
Time domain is the set of non-negative integers.
There are two rules to update the clock.
Rules R1 and R2 to update the clocks are as follows:
R1: Before executing a send, or internal event, process pi
executes the following:
Ci := Ci + d where, (d > 0)
In general, every time R1 is executed, d can have a different
value; however, typically d is kept at 1.
50
Scalar Time
R2: Each message piggybacks the clock value of its sender at
sending time.
When a process pi receives a message with timestamp Cmsg, it
executes the following actions:
Ci := max(Ci, Cmsg )
Execute R1. Ci := Ci + d where, (d > 0)
Deliver the message
d is a non-negative integer value. It can have different values,
but we considered d=1 to identify the time of each event
uniquely at a process.
51
Scalar Time
52
Properties of Scalar Time
1. Consistency: Scalar clocks satisfy the consistency property.
for two events e and f
e → f ⇒ C(e) < C(f)
2. Total Ordering:
Scalar clocks can be used to totally order events in a distributed
system.
The main problem in totally ordering events is that two or more
events at different processes may have identical timestamp.
Example: for events e1 and e2, C(e1) = C(e2) ⇒ e1 || e2
Third event of process P1 and second event of process p2 have
identical scalar timestamp. Therefore, we need a tie-breaker
mechanism. 53
Properties of Scalar Time
2. Total Ordering:
A tie among those events with identical timestamps (scalar) is
broken on the basis of their process identifier.
The lower the process identifier in the ranking, the higher the
priority.
The timestamp of an event is denoted by a tuple (t, i), where t is
its time of occurrence and i is the identity of the process where it
occurred.
The total order relation ≺ on two events x and y with
timestamps (h,i) and (k,j), respectively, is defined as follows:
x ≺ y ⇔ (h < k or (h = k and i < j))
54
Properties of Scalar Time
3. Event counting:
If the increment value d is always 1, the scalar time has the
following interesting property: if event e has a timestamp h, then
h-1 represents the minimum logical duration, counted in units of
events, required before producing the event e;
We call it the height of the event e.
In other words, h-1 events have been produced sequentially
before the event e regardless of the processes that produced
these events.
For example, in Figure 3.1, five events precede event b on the
longest causal path ending at b.
55
Figure 3.1:
56
Properties of Scalar Time
4. No Strong Consistency:
The system of scalar clocks is not strongly consistent; that is, for two events e
and f ,
C(e) < C(f) ⇒ e → f
For example, in Figure 3.1, the third event of process P1 has smaller scalar
timestamp than the third event of process P2. However, the former did not
happen before the latter.
The reason that scalar clocks are not strongly consistent is that the logical
local clock and logical global clock of a process are squashed into one,
resulting in the loss causal dependency information among events at different
processes.
For example, in Figure 3.1, when process P2 receives the first message from
process P1, it updates its clock to 3, forgetting that the timestamp of the latest
event at P1 on which it depends is 2.
Strong consistency requires vector clocks. 57
58
Vector Clock
In the system of vector clocks, the time domain is represented
by a set of n-dimensional non-negative integer vectors.
Unlike scalar clocks (which assigns a single value to each
process), the vector clocks maintain a vector of logical time
values, with each element in the vector corresponding to a
specific process.
If there are n processes then each vector clock consists of n
logical time values.
59
60
61
62
63
64
65
66
67
68
69
70
Software “Clock” 3: Matrix Clocks
In a system of matrix clocks, the time is
represented by a set of n × n matrices of non-
negative integers.
Each event has n vector clocks, one for each process
The ith vector on process i is called process i’s
principle vector
Principle vector is the same as vector clock before
Non-principle vectors are just piggybacked on
messages to update “knowledge”
71
Software “Clock” 3: Matrix Clocks
For principle vector C on process i
Increment C[i] at each “local computation” and “send” event
When sending a message, all n vectors are attached to the
message
At each “receive” event, let V be the principle vector of the
sender. C = pairwise-max(C, V); C[i]++;
For non-principle vector C on process i, suppose it
corresponds to process j
At each “receive” event, let V be the vector corresponding to
process j as in the received message. C = pairwise-max(C, V)
72
Matrix Clock Example
(1,0,0) (2,0,0) (3,0,0)
(0,0,0) (0,0,0) (0,0,0)
(0,0,0) (0,0,0) (0,0,0)
user1 (process1)
(0,0,0) (0,0,0) (2,0,0)
(0,1,0) (0,2,2) (2,3,2)
(0,0,0) (0,0,2) (0,0,2)
user2 (process2)
(0,0,0) (0,0,0) (2,0,0)
(0,0,0) (0,0,0) (2,3,2)
(0,0,1) (0,0,2) (2,3,3)
user3 (process3)
73
74
75
