Synchronization

Module 3
Introduction :
• The processes in distributed systems communicate with each
other
• It is necessary to understand, how do processes cooperate and
synchronize with each other

• Issues…
– How are critical regions implemented in distributed
systems,
– How are resources allocated?

• The techniques used in single CPU system are no longer valid

for processes running on different machines.
Need of Synchronization:

• In a distributed system, there are multiple

processors.
• Hence multiple processes may sometimes need to
agree on the ordering of events
– For e.g. whether message m1 from process P1
was sent before or after message m2 from
process P2.
Needs for precision time
• Stock market buy and sell orders
• Distributed network gaming and training
• Aviation traffic control and position reporting
• Multimedia synchronization for real-time
teleconferencing
• Event synchronization and ordering
• Network applications
Clock synchronization:

• Synchronization in distributed systems is more difficult

compared to centralized ones as they have to use the
distributed algorithms.
• The distributed algorithms have following properties:
– The relevant information is scattered among multiple
machines.
– A single point of failure should be avoided.
– No common clock or other global time source exists.
• Achieving synchronization without centralization requires
doing things in a different way from traditional operating
systems.
• Every computer needs a timer(called computer clock)to keep
track of current time.

• In a uniprocessor system, when a process wants to know the

time, it makes a system call & the kernel tells it.

• If process A asks for the time, & the little latter process B asks
for it, the value that B gets will be slightly higher than (or
possibly equal to )the value that A gets.
• This is not the case when two processes call for time from two
different machines at the same time.
• One processor’s clock may be faster than the other.
– For e.g., in UNIX the large programs are split into multiple
files
• So that change in one source file requires only one file
to be recompiled, not all files.
• Consider UNIX make command…
– When the programmer has finished changing all the source
files, he starts make,

– Which examines the time at which all the source and object
file were last modified.

– If the input file input.c has time 2151 & corresponding

object file input.o has time 2150,
• Make understands that input.c has been changed after input.o was
created, hence, input.c should be recompiled.
– On the other hand, if abc.c has time 2000 & abc.o has time
2001, no recompilation is needed.
 Make

2144
2143

Output.o created Output.c created Make will not

recompile Output.c
• Now, consider what happens in a distributed system, in which
there is no global agreement on time.

• Suppose that output.o has time 2000 & shortly there after
output.c is modified (on diff m/c), but is assigned time 1999,
as the clock on it is slightly behind.

• So make will not call the compiler.

• Hence, the resulting executable binary program will contain a

mix of object files from the old source & new sources giving
wrong results.

– REASON : ….The clocks were not synchronized!!!

How are computer clocks implemented?????
• All computers have a circuit for keeping track of time…called a TIMER.
• A Computer clock has three components:
– a machined quartz crystal that oscillates at a well-defined frequency.
– A counter register.
– A holding register.
• Holding register holds a value.
• Value in counter register is decremented by 1 for each oscillation of the
quartz crystal.
• When the value of the counter register becomes zero, an interrupt is
generated & its value is reinitialized to the value in the holding register
• Each interrupt is called clock tick.
• With a single computer system, & a single clock, it does not
matter if this clock is off by a small amount.

• Since all processes on the machine use the same clock, they
will still be internally consistent.
– For e.g. If input.c has time 2001 & file input.o has time
2000, make will recompile the source file,
• Even if the clock is slow by two units, & the real times
are 2003 and 2002 resp.

• As soon as multiple processors are introduced, each with its

own clock, the situation changes.
• It is impossible to guarantee that the crystals in different
computers , all run at exactly the same frequency.

• In practice, when a system has ‘n’ computers, all ‘n’ crystals

will run at slightly different rates.

• Eventually, the machines go out of synchronization & give

different output when read out.
• The difference in time value is called ‘clock skew’

• What is needed here is Synchronization

………..Synchronization of all the clocks with a
standard time.
Clock Skew

• Computer clocks, like any other clocks tend not to

be in perfect agreement !!
• Clock skew (offset): the Clock skew (difference
between the times on two clocks |Ci(t) – Cj(t)|
Clock Drift:

• Clock makers specify a maximum drift rate ρ(rho) sec/sec.

• By definition

• Where, C(t) is the clock’s time as a function of real time.

• In distributed system, there are several nodes,
each with its own clock running at its own speed.

• Hence, periodically, all the clocks need

resynchronization.
 Clock synchronization issues

➢ Practically no two clocks can be perfectly synchronized

➢ A set of clocks are said to synchronized if their clock skew less
than some constant(∂)
➢ Clock synchronization requires each node to read other nodes’
clock
➢ Time must never run backward
Clock synchronization algorithms
Broadly classified into two types
1. Centralized algorithms
2. Distributed algorithms
Centralized algorithms
❖ In this mechanism, one node has a real time receiver.
This node is called TIME SERVER NODE and clock
time of this node is used as a reference.
❖ The clocks of all other nodes are synchronized with
respect to time server node
❖ Two types of clock synchronizations (Active, Passive)
Passive time server centralized algorithms
➢ In this method. Each node periodically sends a message to the
time server
➢ When the time server receives the message, it quickly responds
with current TIME message (T)
➢ Unpredictable variation of message passing duration effects on
‘T’
➢ Message passing duration is considered based on a threshold
value.
Active time server centralized algorithms
➢ In this scheme, the time server periodically broadcasts
it clock time.
➢ The other nodes receive the broadcast message and use
the clock time in the message for correcting their own
clocks.
➢ Each node has a priori knowledge of the propagation
delay
Disadvantages
❖ These are subject to single point failure – Time server
fails, synchronization cannot be performed
❖ Makes system unreliable
❖ Propagation delay is unpredictable
 Distributed algorithms
➢ Externally synchronized clocks are also internally synchronized
➢ Each node of the system are synchronized wrt real-time server
➢ Multiple real-time clocks are used
Global averaging
❖ The clock process at each node broadcasts its local clock time in
the form of ‘resync’ message (Resynchronization)
❖ It takes the average of the estimated skews and use it as the
correction for the local clock
❖ The estimated skew is compared with threshold value
❖ It discards highest and lowest estimated skews
❖ Calculates the average of the remaining skews
Localized averaging
❖ In this approach, all the nodes of the distributed
system are logically arranged in some pattern ( Ring,
grid, etc)
❖ Periodically, each node exchanges its clock time with its
neighbors in the ring or grid
❖ Set the clock time to the average of its own and clock
times of neighbor
Event Ordering

• A=100; B=100 ;
• A’=(100+100)+10%=220
• B’=(100+10%)+100=210
• Updates need to be performed in the same order at all
sites of a replicated database.
Logical clocks:
• For distributed purposes, it is sufficient to know that, all
machines agree on the same time order.

• RELIABLE WAY OF ORDERING EVENTS IS

REQUIRED

• It is not essential that the time also agrees with the real
time.

• Hence, it is internal consistency of the clocks that matters,

and not whether they are close to real time.

• These are said to be Logical clocks

• There is a clock Ci at each process pi

• The clock Ci can be thought of as a function that assigns a

number Ci(a) to any event a, called the timestamp of the
event a, at pi.

• These clocks can be implemented by counters and have no

relation to physical time.
Lamport clocks:

• Lamport showed that what usually matters is not

that all processes agree on exactly what time it is,
but rather that they agree on the order in which
events occur.

• In the ‘make’ example, what matters is whether

input.c is older to input.o or is newer.
Lamport’s algorithm
• Consider three processes running on different machines,
each with its own clock, running at its own speed.
• When the clock has ticked
6 times in p0,
it has ticked 8 times in p1 &
10 times in p2.
• Each clock runs at a constant rate , but the rates are
different due to differences in crystals
Lamport’s algorithm :

Process 0 Process 1 Process 2

• These values are clearly impossible and must be
prevented.
• Lamport’s algorithm is used to correct this situation.
• Since message C left at 60, it must arrive at 61 or later
• Each message carries the sending time according to the
sender’s clock.
• When a message arrives and the receiver’s 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.
• Hence, C arrives at 61 and D arrives at 70.
Correction using Lamport’s Algorithm:

Process 0 Process 1 Process 2

• Between any two events, the clock must tick at least once.

• When all the events in the system are completely ordered,

there can be situation in which, two events take place
exactly at the same time.

• Hence, both the events will have exactly the same time
stamp, say 100

• But if the events have to be totally ordered, no two events

can take place at exactly same time.

• Hence, one event is given time 100, and the other is given
time 100.1
System Model :

• System: Collection of processes

• Process: Sequence of events
• Event: Execution of a subprogram or single instruction, message send
& receive.
• A distributed system is a collection P of sequential processes pi,
i= 1,2,…N.
• A process pi has state si
• Each process pi executes a sequence of actions
– Sending a message;
– Receiving a message;
– Performing an internal computation that alters its state si;
• The sequence of events within a single process pi are totally ordered
Happens before relationship:

• To synchronize the logical clocks, Lamport

defined a relation, called Happens-Before
relationship.

• Expression a→b is read as “event a happened

before event b”.
 The happens-before relation is observed in
two situations:
1. If a & b are events in the same process, & a occurs before b,
then a→b is true

2. If a is an event of a message being sent by one proces, & b is

the event of message being received by another process,
then, a→b is true
As the message can not be received before it is sent.
Happens-before relation is a transitive relation. i.e.
If a→b and b→c then a→c is true.
Concurrent events:
• If two events x and y happen in two different processes,
and they do not exchange messages with each other
(Don’t communicate), then neither x→y nor y→x is true.

• We cannot say whether which one event happened before

the other.

• These events are said to be concurrent. Indicated as (a||b)

• For any two events a and b in a distributed system,

either a→b or b→a or a||b
• In a happens-before relation, we need to assign time
for every event a C(a) on which, all the processes
agree.

• These time values should have a property that, if

a→b, then, C(a) < C(b).

• Also, the clock time C should always go forward

(increasing) and never backward (decreasing).
Using Lamport’s algorithm, all the events are
assigned time, subject to following conditions:
• If a happens before b in the same process, then,
C(a) <C(b).

• If a and b represent the sending and receiving

events of the same message, then, C(a) < C(b).

• For all events a and b, C(a) != C(b).

How does a Lamport clock advances??
• The processes’ clock values are assumed to be zero
initially.
• The clock is incremented by one between any two
successive internal events. Ci:= Ci+1
• The clock is incremented by one for a send message event,
of the respective process.
Exc:1 Assuming the only events are message send and
receive, what are the clock values at events a-g?
Total ordering of events:
• We can order the events in a system based on happened-
before relationship among the events.
• We simply need to order the events by the times at which
they occur.
• But, the happened-before relationship is only the partial
ordering on the set of all events in the system.
• With this event-ordering scheme, it is possible that two
events a and b that are not related by happened-before
relation may have the same timestamps associated with
them.
• In this situation, nothing can be said about the order of the
two events.
• Hence, for the total ordering on the set of all system
events, an additional requirement is wanted:
• No two events ever occur exactly at the same time.
• To fulfill this requirement, Lamport proposed the use of
total ordering of the processes.
• He suggested use of process id along with the timestamp
value.
• Using this method, we can assign a unique timestamp to
each event in the system, and get the total ordering of all
events in the system.
Exc:2 Find Lamport clock values for the
following scene
Ans:2
 Clock synchronization
• Ordering of events taking place in processes
of a distributed system according to their
temporal association.

• Required to ensure mutual exclusion to

guarantee serialization of concurrent access
to shared resources.
 1. Christian’s Algorithm
• To keep absolute time, Christian's algorithm
proposes the concept of a time server,
typically a UTC (Coordinated universal time)
server.
• The machines are periodically expected to
make an RPC (Remote ProcedureCall) to
obtain time from this server.
• A machine adjusts its time according to the
following algorithm.
 Christian’s Algorithm(conti…)
• Let T0 be local system time at which the
request is sent by process P of a node, and T₁
be time at which the response is received at P.
• Round trip delay time (RTT) = T1- T0
• The estimated overhead due to the network
delay in each direction is then
(T1 - T0) / 2
• The new time Tp at P can be set to the time
returned by the server plus the time that
elapsed since the server generated the
timestamp, that is,
Tp : Ts + (T1- T0) / 2
• For example, if T0= 19 and T1 = 27 then
(RTT)/2 = 8/2 = 4

• If Ts, is 16, then Tp = 16 + 4 = 20 will be

absolute clock time adjusted at process P
Christian’ Algorithm(conti…)
Christian’s Algorithm(conti…)
⮚ Uses a time server to synchronize clocks

⮚ Mainly designed for LAN

⮚ Time server keeps the reference time (UTC-Universal Coordinated

Time)

⮚ A client asks the time server for time, the server responds
with its current time T, and the client uses the received
value T to set its clock

⮚ But network round-trip time introduces an error

⮚ RTT = response received time – request sent time

(measurable at client)
 2. Berkeley’s Algorithm
• The Berkeley algorithm, developed by Gusella
and Zatti, assumes that none of the nodes
have an accurate time source.
• Thus, it averages the time and synchronizes
all.
• It works in the master-slave configuration.
• The server polls each machine periodically,
asking for their time.
• The time at each machine may be estimated by using
Christian's method to account for network delays.

• When all results are in, the master computes the

average time (including its own time in the
calculation).

• Instead of sending the updated time back to slaves,

which would introduce further uncertainty due to
network delays, it sends each machine the offset by
which clocks need adjustment.

• The clocks at slaves are then adjusted according the

offset.
• Three machines have times 3:00, 3:25 and
2:50.
• The master is with the time 3:00.
• It polls the slaves and sends out a synchro-
nization query to other nodes.
• Each of these machines sends a timestamp
difference as a query response.
• The server now averages the three
timestamps - the two it received and its own-
computing
(25-10+ 0)/3 = 5.
• It sends an offset
(e.g., for slave offset = 5-(-10) = 15)
to each slave so that the slave's time will be
synchronized to the average after the offset is
applied and new I will be calculated.

• The server has to adjust its own time by 0:05.

Berkeley’s Algorithm
Berkeley’s Algorithm