Clock Synchronization

in a Distributed System

1
Topics
• Introduction

• Clock synchronization

• Physical Clock

• Logical clocks

• Election algorithms
Introduction
• Aim is to determine how processes can synchronize.
• It is important that :-
• Multiple processes do not simultaneously access
a shared resource, rather they should cooperate.
• Sometimes , multiple processes need to agree on
the ordering of events.
• Synchronization in distributed systems is difficult

3
Lack of Global time in DS
• It is impossible to guarantee that physical clocks
run at the same frequency
• Lack of global time, can cause problems
• Example: UNIX make
Edit output.c at a client
output.o is at a server (compile at server)
Client machine clock can be lagging behind the
server machine clock

4
 Lack of Global Time – Example

When each machine has its own clock, an event that occurred after
another event may nevertheless be assigned an earlier time.
 Physical Clock….
• Computers have a CMOS clock circuit for keeping track of time.
• Instead of clock , timer is a better word
• A computer timer is a precisely machined quartz crystal, oscillating at a
well
defined frequency
• Associated with each crystal are two registers:
– A Counter , Holding Register

• Each oscillation of the crystal decrements the counter by one. When

counter reaches zero, an interrupt is generated. Each interrupt is called one
clock tick and again counter is loaded with the value of holding register.
• Clock tick have a frequency of 60-100 ticks per second

7
 Physical Clock
The problems:
1. Crystals cannot be tuned perfectly. Temperature and other external
factors can also influence their frequency.
Therefore, two computers will never agree on time .
The phenomenon of clocks ticking at different rates, creating a gap
in the perceived time is known as clock drift
2. Two crystals are never identical.
When a system has n computers , all n crystals will run at slightly
different rates, causing the (software)clocks to get out of sync and
give different values when read out. This difference in time values is
called clock skew.
Therefore, the computer clocks on different processors of the
distributed system show different time.
8
 Need for Precise Time
• Social networking services
• Stock market buy and sell orders
• Secure document timestamps (with cryptographic certification)
• Aviation traffic control and position reporting
• Radio and TV programming launch and monitoring
• Intruder detection, location and reporting
• Multimedia synchronization for real-time teleconferencing
• Interactive simulation event synchronization and ordering
• Network monitoring, measurement and control
• Early detection of failing network infrastructure devices and air
conditioning equipment
• Differentiated services traffic engineering
• Distributed network gaming and training 9
Clock Synchronization

Cristian Berkley
 Passive Time Server…
There is one time server node which is used as a reference time, in
centralized algorithms.

• Each node periodically sends a request message “time = ?” to the

time server to get the accurate time.
• Time – server responds with “time=t”
• Assume , client sends a message at time t0
gets a reply at time t1.
Message propagation time from server to client node is
(t1-t0)/2
• Client node receives a reply, and it adjusts its clock time to
t +((t1-t0)/2
11
 Cristian’s Algorithm...
• Cristian’s Algorithm presents physical clock synchronization

❑ The simplest algorithm for setting time, it issues a Remote

Procedure Call to time server and obtain the time.
❑ A machine sends a request to time server in “d/2” seconds,
where d=max difference between a clock and UTC.
❑ The time server sends a reply with current UTC when receives
the request.
❑ The machine measures the time delay between time server
sending the message and machine receiving it. Then it uses the
measure to adjust the clock.

14
Cristian’s Algorithm….
 Cristian’s Algorithm
To improve the accuracy, :-
– Any measurements in which (t1-t0) exceeds some
threshold is discarded.
Assuming they are due to network congestion and
thus are unreliable.
- The estimates derived from remaining probes are
then averaged to get a better value.

Also, the messages that are received back fastest can be

considered as most accurate ,as it is presumed that it
has encountered less traffic …therefore representing the
pure propagation time . 16
 Berkeley Algorithm…..
• It is also a Centralized algorithm

• Its time server (a time daemon) is an Active Machine.

• The server polls each machine periodically, asking it for the

time.
• When all the results are in, the master computes the average
time.
• It tells all the other machines to advance or slow down their
clocks until some reduction has been achieved.
• However, the time daemons time has to be set manually by the
operator periodically.
17
 Berkeley Algorithm…

a) The time daemon sends synchronization query to other machines in

group.
b) The machines sends timestamps as a response to query.
c) The Server averages the three timestamps and tells everyone how to
adjust their clock by sending offsets.
18
Berkeley Algorithm…
Disadvantages of Centralized
Clock
1. Subjected to single point failure
2. From scalability point of view it is generally not
acceptable to get the time requests serviced by single
time server.
Cristian Berkley

1. It has a passive server 1. It has an active server

2. Server just responds to 2. Server polls machines from

client queries time to time
Network Time Protocol….
• It is a standard followed to synchronize clocks on the Internet.
• Adjusts system clock as close to UTC as possible over the
Internet.
• The standard uses a tree structure to organize the NTP servers.
• Each node requires synchronizing with its parent node.
• Client polls the server to synchronize its clock with remote
server.
• Default port number is 123
• Servers organized as strata
– Stratum 0 server adjusts itself to WWV directly
– Stratum 1 adjusts self to Stratum 0 servers
21
 Network Time Protocol….
• Primary servers are connected directly to a time source. (e.g. a
radio clock receiving UTC, GPS). bers of clients and servers)
• Secondary servers are synchronized with primary servers.
• The servers are connected in a logical hierarchy called a
synchronization subnet. Each level of the synchronization
subnet is called stratum.
NTP Server Primary Server

NTP Server
Secondary Server
NTP Server NTP Server

NTP Server NTP Server NTP Server

NTP Server

Tertiary Server 22
Network Time Protocol….

• A requests time of B at its own T1

• B receives request at its T2, records
• B responds at its T3, sending values of T2 and T3
• A receives response at its T4

24
 Summary
Summary

• Real synchronization is imperfect.

• Clocks never exactly synchronized.
• Often inadequate for distributed systems
– might need totally-ordered events

– might need millionth-of-a-second precision

Logical Clocks

29
Logical Clock…
● Assumes no central time source –
● Logical clock assigns timestamp(sequence number) to
events for sequencing them in the order agreed upon
by all processes.
● The timestamp is the agreed upon relation amongst
the events.
● This timestamp style event ordering is called termed
as logical clock .

30
Logical Clock
If a and b are 2 events, a b, would mean that a “happened before” b
1. If a is the event corresponding to the sending of message m in one process,
and
b is the event corresponding to receiving the same message m in another
process.

C1(a) P1
t

t
C2(a) P2
1. If a and b are events internal in the same process
a b

C1(a) C2(b)

One can assign logical time by assigning a time value to the events a and b.
If a b, then clock(a)< clock(b) as time cannot run backwards.This
monotonicity
property is called the clock consistency condition .
31
Lamport’s Timestamps
• To synchronize logical clocks, Lamport defined a relation called happens - before
.

• a ‘Happened Before’ b : a→b

Situations:
1. If a and b are events in the same process, and a comes before b, then a → b.

1. If , a :event of message sent

b : event of receipt of the same message
then a → b.

1. HBR is Transitive:
If a → b and b → c then a → c.

Note: Two distinct events a and b happens in different process that do not
exchange messages then these events are said to be concurrent
a -/->b and b -/->a
33
 Implementation of Logical clocks
Conditions for correct functioning:
• C1: If a and b are two events in the same process, and a→ b,
then we demand that C(a) < C(b).
• C2: If a corresponds to sending a message m, and b
corresponds to receiving that message, then also C(a)<C(b).
• C3: A clock C associated with the process P must always go
forward, never backwards.

Hence corrections to a logical clock must be always made by

adding a positive value , never subtracting from it.
 Lamports Logical clock….

Three processes, 3 machines, each with its own clock. The clocks run at different
rates.
Clock has ticked 6 times in P0 , 8 times in process 1 and 10 times in process 2.
 Lamport’s Logical Clocks

Lamport’s algorithm corrects the clocks.

• At time 6, process 0 sends message m1 to process 1 .
• At P2, the clock in process reads 16. So it will be
concluded that it took (16-6), 10 ticks to complete the
travel.
• Message from P2 starts at 24 and reaches P3 at 40.

Message from 60 , reaches at 56 in Process 2 , Not

possible
Similarly, m4 leaves at 64 and arrives at 54
It is this situation that needs to be prevented.

38
• Lamports solution follows from the happens-before
relation.
Since C left at 60, it must arrive at 61 or later.
• Therefore, each message carries the sending time
according to the senders clock.

When a message arrives and the receivers clock shows a

value prior to the time the message was sent , the
receiver fast forwards its clock to be one more than the
sending time .
So, m3 arrives at 61.and m4 arrives at 70
39
 Rules for adjusting clocks
• To meet the global time requirements, between
every two events , the clock must tick at least
once.

• For two events a and b in same process p1

• C(b)= C(a)+1

• If a is sending process and b is receiving process

of pi and pj then,
• Cj(b)=max((Ci(a)+1),Cj(b))
41
Position of logical clocks in
Middleware
 Vector Timestamps….
● With Lamport timestamp, nothing can be said about the
the relationship between 2 events a and b by comparing
their time values C(a) and C(b).
ie. If C(a) < C(b), it does not imply that a happened before
b.
● Casualty can be captured by means of vector timestamps.
● A vector timestamp VT(a) assigned to an event a has the
property that if VT(a)<VT(b) for some event b, then event a
is known to casually precede event b.
 Vector Timestamps….
They are constructed by letting each processPi maintain a
vector Vi with the following 2 properties :-
1. Vi[i] is the number of events that have occurred so far at Pi
This is maintained by incrementing Vi[i] at the occurrence
of each new event that happens at process Pi.
1. If Vi[ j ] = k , then Pi knows that k events have occurred at
Pj
This is maintained by piggybacking vectors along with the
messages that are sent .
When Pi sends message m, it sends along its current
vector as a timestamp vt.
 Vector Timestamps….
Consider the example below :

P2

P3

● P1, P2 and P3 are three processes,their vectors are initialized as V[0,0,0]

● Event A occurred at P1 , so the 1st element of vector V1 is incremented (note :
this is neither a send or received). So V1[1,0,0]
● Event B also happens at P1, but is a send event , so the 1st element is again
increased and the value of the vector V1[2,0,0]
● This vector V1 is sent with the message to receiver process P2. 50
Vector Timestamps….

P2

P3

● Meanwhile, event 1 at P3 with associated vector as V3[0,0,1]sends a message and

its vector V3 to the receiver P2.
● Process P2 with vector V2[0,0,0] now receives this message as V3’ and marks this
event as E.
● To update vector V2, the 1st element of the vestor ha sno change (no information
about events at P1, here sender is P3 and receiver is P2)
● the 2nd element is incremented by 1 (received event is happening at P2 ) and for
the 3rd element in the vector, max(V2[3],V3[3] , that is max(0,1) = 1 is
calculated.
● The vector V2 is V2[0,1,1] for event E.
● Event F, which again is a receiver event at P2, requires vector calculations for
V2 to
be done using the vector of P1, V2[max(0,2), 1+1,1] ie. V2[2,2,1]
● Similarly all vectors for all events are updated.
51
 Important Lessons
• Clocks on different systems will always behave differently
– Skew and drift between clocks

• Time disagreement between machines can result in

undesirable behavior

• Two paths to solution: synchronize clocks or ensure

consistent clocks

• Clock synchronization
– Rely on a time-stamped network messages
– Estimate delay for message transmission
– Can synchronize to UTC or to local source

53