Lecture 13

IIT Kanpur July 201
20 followers
Feb 29, 2024
time and clock synchronization I am Dr
rajim Mishra working as professor in the
department of computer science Indian
Institute of Technology
Patna content of this lecture in this
lecture we will discuss the fundamentals
of clock synchronization tion in the
cloud and the different
algorithms we will cover causality and a
general framework of logical clocks and
present two systems of logical clock
namely the Lamport and the vector time
stamps to capture casuality between the
events in a distributed
system now first let us understand the
need of synchronization that is need of
clock
synchronization suppose you want to
catch a bus at 9:05
a.m. but your watch is off by 15
minutes what if your watch is late by 15
minutes you will miss the
butts what if your watch is Fast by 15
minutes then you will end up unfairly
waiting for a longer time than you
intended so there may be examples
of such kind of problems where if your
watch is late by 15
minutes
then you will miss the bus or maybe some
event and if your watch is Fast by 15
minutes then you will end up unfairly
waiting for a longer time than you
intended so the time synchronization is
therefore required for ensuring the
correctness and the fairness so
correctness if it is not guaranteed that
means if the clock if your watch is late
by 15 minutes then the event will happen
before your watch is giving you that
time therefore you will miss that event
and this is the problem of
correctness second problem is that if
your watch is Fast by 15 minutes then
you will reach early to catch a bus and
unfairly waiting for longer than you
intended and this problem is about the
fairness so there is a need of clock
synchronization that is neither so it
has to ensure both correctness and the
fairness
together
so let us now understand about the time
and
synchronization so uh as far as the
distributed time is concerned the notion
of time is well defined at each location
but the relationship between the time at
different location is quite unclear and
that is called the distributed
time so the time synchronization is
therefore as we have told in the
previous slide that time synchronization
leaded for correctness and
fairness
purposes now considering why the clock
synchronization is needed in the cloud
computing system take the example of a
cloud-based Airline reservation system
now let us take a particular server
X so a
client
so a client one request to purchase a
ticket the last ticket on the flight say
pqr 1 2
3 it want to purchase this ticket the
server time is time the purchase using
its local clock
as
625
and then lcks it and replies
okay at this time it will say okay to
the client because there is one seat
left so that was the very last seat and
the server X send a message to the
server y so server y saying that the
flight is full for example here there is
server y so it will say that now the
server so that the flight is
full which flight that is
pqr 1 2 3 4 is full after booking this
particular
ticket now y
enters pqr is full and its local clock
value is 6:00
than 20 minutes it will point out that
the flight is full now server
Zed queries X logs and y's
logs but server Z will confuse why
because the ticket was booked at
625 as per as the timing of the server X
is concerned but server y tells that
620 the flight was full and it was
booted so this may lead to the incorrect
actions at The Zed here in this case
because 625 the the ticket was booked
and before that time it was showing that
the flight was full because
of the two different clocks are running
that is at Y and at X
and both the time when they are being I
mean taken at Zed so it will be an
incorrect action being performed based
on these
timings so therefore in a cloud
application where multiple servers are
running there also requirement of a
clock
synchronization in various applications
now therefore the key challenges is that
the end host in the internet based
systems like like Cloud where each
server has its own clock and CPU within
one server or work sttion they share the
common system clock so the processes in
the internet based system following
asynchronous
model that is no bounds on the message
delay and the processing delay so unlike
multiprocessor that is a parallel
Computing system which follows the
synchronous
model
so let us understand with some of the
definitions and then we will formulate
the problem so asynchronous distributor
system consist of number of processes
and each process has a state there that
is being measured by the
variables and each process will take the
action to change its state which may be
instruction or a communication action
that is by send and receive so an event
is the occurrence of an event event and
each process has a large
clock that is nothing but an event
within a process that can be assigned
time is time and thus order
linearly in a distributed system we also
need to know the time the order of the
event across the
processes so let us take this particular
fact by a diagram which is called a
state time diag space time diagram space
means these processor P1 P2 and
P3 they are the distributed system
processor running at different
geographic location locations that is
why this
space is
being has been there and for each
process P1 now it will run its events
using the same block called internal
events in the internal events there are
two specific event one is the massage
send event which which will communicate
across the processors and
message receive event also communicates
across the processor and all other
events are called internal events and
the SpaceTime diagram of the distributed
execution is shown here as an
example now coming to the physical clock
synchronization there are two different
issues one is called clock skq the other
is called clog
drift now each process that is is
running at some and host has its own
clock now when you compare two clocks at
two different processes they exhibit a
clock is q that is the relative
difference in the clock values of two
different
processes then there is a concept which
is called a clock drift that is the
relative difference in the clock
frequency rates of the two processes so
a non-zero clock is
Q implies that the clocks are not
synchronized they are giving different
timings
a non-zero clock drift causes theq
increases
eventually so if a this is just like a
faster vehicle is ahead it will drift
away and if a faster vehicle is behind
it will catch up and then Drift Away now
coming to the clock in accuracies so
clocks that must not only be
synchronized with each other but also
have to adhere to the physical clocks
are termed as physical clocks the
physical clocks are synchronized to an
accurate realtime
standards however due to the clock
inaccuracy a timer or the clock is set
to be working within a specification
where the constant row is the maximum
skew rate specified by that manufacturer
which is shown over
here
now the maximum drift rate of a clock so
absolute MDR that is the maximum drift
rate is defined to the relative
coordinated universal time UTC is the
correct time at any point of time so MDR
of any process depends on the
environment so the maximum drift rate
between the two clocks with the similar
MDR is 2 * MDR so given a maximum
acceptable is q m between any pairs of
the clock it need to synchronize at
least once
every that is M divided by 2 multili by
MDR time
units in this case now internal
versus external versus internal
synchronization now consider a group of
processes so external synchronization
that is each process CI is clog is
bounded d of a well-known clock s
external to the to the
group so let us say CI is the process
I's clock value and now a well-known
clock s is an external so c i minus s if
you take the absolute value has to be
now bounded by D at all point of time
called external
synchronization so external clock may be
connected to the universal qu at a time
or an atomic clog so external
synchronization is done by two different
algorithms one is called Christian
algorithm the other is called Network
time
protocol internal synchronization does
not require an
external Universal Coordinated Time or
atomic clock so every process every pair
of process in a group have the clock
within the bound D that is if let us say
two process processes their internal
clock CI and CG the absolute values
should be less than bounded by D at all
point of time then it is called internal
synchronization the two algorithms very
commonly using the internal
synchronization called Barkley algorithm
and data center time
protocol now external synchronization
with with
d is same as implies that internal
synchron with
2D that is internal synchronization does
not imply the external synchronization
achieved so let us see some of the basic
fundamentals of external time
synchronization so here you can see that
all the processes P will synchronize
with the time server s using the message
exchange so what's wrong here in this
case so P will send a message what's the
time and S will respond here is the time
t
and it will set the clock with the time
T so what is wrong here in this
particular way of synchronizing the
clock by the time message has received
at P
here the time has moved
on the time has moved on and
piece time set to T is
inaccurate so inaccuracy a function of
the message latency and some latencies
are unbounded in asynchronous system the
inaccuracies cannot be
unbounded so let us see about the
Christian algorithm so Christian
algorithm says that if let us say p
measures the round trip time that is rtt
of a message exchange suppose we know
that the minimum of P to S latency is
called Min
one and the minimum s2p
latency is called bin
2 so Min one and Min 2 now depends upon
the operating system overhead to buffer
the messages TCP time to Q the message
and so on so the actual time at
P when it receives a response is between
t plus here let us say it's t so
t + Min
2 this is t
+ Min
2 add to t+
rtt t+ rtt minus Min one this
one t+ rtt minus
min1 so the actual time at P when it
receives the response is between t + Min
2 and t + rtt t plus rtt
minus mean one that is this
one and this
one so p sets its time to the halfway
through this particular interval that is
t+ rtt + M2 minus Min 1 ided 2 so error
is at the
rtt minus
min1 minus min2 ided 2 and it is being
bounded so these are the error bounds so
error will be in terms of
T1 minus this is T1 minus t0 / 2 minus t
Min now the error bounds are already
there there's aot owed to increase the
clock value but should never decrease
the clock value May violate the ordering
of the events within the same
process now this error bounds is allowed
to increase or decrease the speed of the
clock if the error is too high take
multiple readings and average
them so Christian algorithm is explained
again here in this particular example
let us say that send
request is at by :00 508 and receive
response is at
5085 900 was 1,500 so the response
contains
519 25 300 that is T server elapse time
is T1 minus t0 that is 900 minus 100
that is 800 milliseconds is the elapse
time that is shown were here now the
time St was given
400 milliseconds ago here can
guess so you can set the server time is
T server time plus the elapse time that
is 300 + 400 that
700 so that is what is shown with in
this particular case now if you can
measure the error so 900 minus 100
divided 2 -
200 so here you can see this particular
900 900 is the active response 900 is
this one 900 minus 100 ID 2 -
200 is equal to 800 divided and that is
plus - 200 that is an error which is
bounded now another protocol is called
Network time protocol
and network time protocol became the
internet standard that is RFC
1305 Network time protocol servers they
are organized in the form of a
tree now each client here is a Lea opet
Tre and each node synchronizes with its
parents so let us see about the network
time
protocol here in this case uh child will
send a message let's start the protocol
the parent will send the message
one and its time of time stamp at 1 when
it will receive let us say it will
receive the message it will make the
time called receive time tr1 and then it
will prepare a message to with a time
stamp called TS2 and the message two
will
receive the message at time tr2
and it will send the message with this
time stamp one and time stamp two all
the time stamps that is time stamp one
time is St tr2 and then time St tr1 and
TS2 all are available to the child and
using all four time
stand it will calculate an
offset which is tr1 minus tr2 + TS2
minus ts1 divided 2 this is called an
offset and let's calculate the error now
let us say the real offset is oral so
child will be ahead of the parent by
Oral plus and parent will be ahead by
child minus
oral suppose one way of the latency of
the message one is L1 and let us see
that nobody knows about L1 and L2 so TR
R1 isal to ts1 + l1+ oral and tr2 isal
TS2 + L2 minus oral now then if you take
these two equ equations and you subtract
the second one from the first this is
the first
equation and this is the second
equation so 2 - 1 if you take in this
case you will get an oral of this uh
point and if you if you see this is uh
this this is nothing but small o that we
have already
defined then minus L2 - L1 divided by 2
so oal minus o becomes L2 minus L1 ided
2 which is also an upper bound with L2 +
L1 ided 2 and this is nothing but a
roundt trip time so error is bounded by
the round trip
time so bar
algorithm was given in
1989 now here the master pulls each
machine periodically ask the machine for
the time for that it can use the
Christian algorithm to compensate the
network latency now when the results are
in compute include the Master's time and
hope that average cancels out the
individual flux tendency to run faster
than slow so send the offset by which
each clock needs adjustment to each
slave and avoids the problem with the
network
delas so bar algorithm is stated using
this particular example now you can see
that it is there are three different
processes the
325 and uh 250 and so
on so bar algorithm uh can be stated
using this particular diagram can see
that the master now will take the clock
values of all the clients so the barl
algorithm um is shown over here so it
will compute the qu tolerant average
here in this case by taking all three
clock values and now it will not use one
of these outl that is 9 or 10 is an outl
compared to 325 and 250 and 3 so in the
average it will take only the relevant
time and outliers will be eliminated uh
in the barlay algorithm and once it is
calculated
305 then now it
will uh be able to uh to offset it will
send that uh 325 that means it will take
away the
20 of it uh similarly uh in this case uh
it will be uh plus because 215 so 305
means uh + 15 and it will now then
reduce minus 605 here in this case now
coming to the data center time protocol
dtp now dtp is a globally synchronized
time versus via the data center Network
so data data center time protocol uses
the physical layer of the network
devices to implement the decentralized
clock synchronization protocol it is
highly scalable with bounded precision
and um so so there is uh it is an
internal clock synchronization algorithm
as we have said there are two types of
clock synchronization so data center
time
protocol is is a internal clock
synchronization where end to end is 200
NS
so here you can see that uh it runs in
two phases between two peers initial
phas is me measuring this particular
time and then it will perform the
resynchronization and uh and so on so
this uh particular uh diagram shows
about the physical layer that is of of
the switches and data center time
protocol has the property that provides
the bounded Precision scalability in the
hardware and is bounded by 4T and uh
this is all uh being calibrated and but
still it has a non-zero error so the
question is how to get rid of the error
can be synchronize the clock Al together
and still be able to order the events so
why the clock synchronization is needed
is to order the events and distributed
system so physical clock synchronization
has now an error bound even after the
synchronization so therefore uh let us
see some of the issues which is related
to the clock synchronization ordering of
the event without having the physical
clock synchronization now to order the
event across the processes which are
trying to synchronize the clock is an
approach that we have seen called
physical clock
synchronization now what if we instead
assign the time stamp to the events that
was not the absolute time so as long as
these time stamp obey causality that
would work so if an event a Cally
happens before another event B then the
time stamp of a is less than time stamp
of B now this logical or Lamport
ordering of The Logical clock was
proposed by lesie Lampard in
1970 and is almost used and is used in
almost all the distributed systems since
then and almost all the cloud computing
system use some form of The Logical
ordering of the events so lampard's
research contributions are summarized
over here and it has laid down the
foundation of distributor system and
today's Cloud the notable papers notable
works
are the time clock and ordering of
events in a distributor system which has
got
to him conferred with an poy influential
paper award in 2000 how to make
multiprocessor computer that correctly
executes multiprocess
programs the bantine journals program
distributed
snapshots and part-time Parliament all
these papers are seminal papers and they
have being contributing to the today's
cloud computing so it's worth mentioning
here so these paper relate to the
concept such as logical clocks bantine
failures and they are the most cited
papers in the field of computer science
and describe the
algorithm in a distributed system so
pxas algorithm for consensus Bakery
algorithm for Mutual exclusion of
multiple threats in the computer system
that require the same resource at the
same time CH Lepard algorithm for
determin for determination of a
consistent Global State
snapshot the lampart signature is one of
the Prototype of a digital signature so
let us start with the
Lamport or The Logical ordering so it
will Define The Logical relation that is
happened before relation among the pair
of events and this relation is mentioned
by this particular relation symbol now
happen before relation has governing
three different rules the first says
that on the same process that is the a
happened before B this means the time
stamp of a should be less than the time
stamp of B similarly if a sends a
message M to P then send off the message
M has happened before the receive of a
message M so together rule one and Rule
two is being used in defining the
transitivity relation that is if a is
happened before B and B is happened
before c this implies that a has
happened before c and together this
particular relation happened before Rel
creates a partial order among all the
events in the distributed
system why it is called partial order
because not all the events are being
related with this happened before
deletion that is why it is it is a
partial order take this particular
example in A Spacetime diagram of a
happened before relation so a has
happened before B if let us say that A
and B they are all internal
events
B is happened before
F so B is happened before F this can be
seen that B has happened before E B has
happened before e and e is happened
before f using transitivity B has
happened before F and that is what is
correct over here a has happened before
F so a and
F now you can see that uh a is happened
before B and then B is happened before
before F so a has happened before F here
in this particular case of the example
similarly you can also check whether H
has happened before G or not so H has
happened before
G so let us see that H has happened
before E using send off message then e
has happened before uh f
e has happened before G so therefore H
has happened before g f has happened
before J so F has happened before
G so F has happened before d and e and
and E is happened before D and J is
happened before E therefore F has
happened before g c has happened
before J can also be concluded in the
same
way now coming to the lampart time stamp
the goal is to assign the logical or
lampart time stamp to each
events time is time and that obeys the
cality so rule one says that each
process use the local counter that is
the clock which is an integer initially
the count count clock initially the
counter is initialized to zero and each
process increments the counter when the
send or an
instruction happens at it so the counter
is assign into the event as its time
stamp send off message uh event carries
its time stamp receive of a marage
message event uh the the counter is
updated by the max of local clock and
the message time stamp plus one so here
you can see that particular clocks are
initialized to zero then the first event
is time stamp one and the second event
will be measured by taking the maximum
of local time and the message which it
carries the time plus one so maximum of
zero so here it maximum of zero that is
the local
time
and there is a local time maximum of
zero and one is the time which is being
carried here in this particular message
that will end then plus one so it
becomes two so the value is two here in
this case
similarly you can calculate the time
stamp here so the local time is two that
is over here and the message also will
contain the time two two maximum of two
and two is 2 plus one that is three so
time stamp of this par message will
become three here in this case similarly
here the maximum of of this three and uh
four this this particular time is let us
say
three sorry this is three the local time
is three and the the time which is
carried in the message is four and this
is
five now similarly if you see that a has
happened before B this means that the
time stamp of a is less
than the time stamp of B and this is
what they are oing the
city so has happened before G here you
can see that H has happened before
before
G
then the time stamp of H is less than G
and that is it is obing the
city
now in certain cases when C has happened
before F or not when uh C has happened
before F or not since there is no
exchange of messages between C and F
they are not even ordered you know that
using happen before
relation both are having values three in
that
case so this is not correct so such
events which is not governed by happened
before relation they are called
concurrent events they cannot be ordered
in that case so the concurrent event
that is the pair of concurrent doesn't
have the causual path from one event to
another so The Logical time stamps does
not guarantee to be ordered or unequal
for concurrent events so the concurrent
EV is not C is not causality
related so you have to remember that
even as happened before E2 this means
the time stamp of E1 is less than time
stamp of
E2 and the time stamp of E1 is less than
time stamp of E2 this means that E1 has
happened before E2 or E1 and E2 are
concurrent
events now coming to the vector clocks
which are used in the key value
stores such as react so each process
uses the vector of integer clocks
suppose that there are n process in the
group then each Vector has n elements so
process I maintains the vector vi from 1
to n so GTH element of the vector
clock at process I
is a knowledge of the latest events at
the process
G so implementing the vector clocks so
on an instruction or send event at a
process I it increments only its aat
element of its Vector clock so each
message carries the send events Vector
time stamp and receiving the message at
a process I it will increment its own
vector and by by looking up the other
Vector elements it will take the maximum
of the values from the others or from
the local for all the values G which is
not equal to I so let us take the
example so here Vector clocks initially
all values are 0 0 0 here in this case
now this particular clock will be
incremented because it's a internal
event now the next
next event will be you can see that this
is the internal event this is one and it
will be sent in the message when the
message will
receive so the local event is zero will
become one in that case what about other
clock values so the clock values 0 and0
will become zero here in this
case and this will be taken over by
value of two and one one will become one
it is not incremented here in this case
so if you see Cally Cally related events
so vector v vt1 is equal to Vector vt2
if and
only the vectors Vector elements all the
elements when both are equal similarly
Vector T1 is less than or equal to
Vector T2 if for all the events
Vector T1 of r is less than or equal to
Vector T2 the two events are causally
related if if VT one is strictly less
than
vt2 so here you can see that this
implies that if and only Vector T1 is
less than or equal to Vector T2 and
there exist some J such that between uh
between I and N there exist A J such
that this Vector T1 of J is strictly
less than Vector 2 and H it is so two
events V1 vt1 and V2 are concurrent if
neither vt1 is less than or equal to vt2
and not n vt2 is less than or equal to
therefore both are all parallel or
concurent
even Vector clocks OB the casuality for
example is a is happened before B if you
see the vector clocks of a 1 0 0 is less
than 20
0 similarly for B is happened before F
that means the vector clock value of B
is 2 0 is less than 2 to
one similarly um all others which are
shown over here they follow now coming
to the parallel event or concurrent
event you can see that C and F they are
concurent event why because the vector
clock values of c and F is neither
neither C is less than or equal to F nor
f is less than or equal to C hence they
are concurrent
events let us summarize then in that
case about logical time stamp lamp or
time stamp is an integer clocks assigned
to the events obey causality and cannot
distinguish the concurrent events Vector
time is time obey the cality and by
using more space can also identify the
concurrent events
so conclusion is that the clocks are
unsynchronized in a asynchronous
distributor system but need to order the
events across the processes in the
distributed system physical clock
synchronization algorithms Christians
Bist Network time protocol data center
time protocol has an
error function of round trip time you
can avoid the time synchron altogether
by inad assigning The Logical time stamp
to the to the events thank
you
