Distributed Systems

lecture 09
SYNCHRONIZATION
 Coordination and Synchronization

• In centralized systems, time is unambiguous

• If a process asks for the time and a little later it

asks for the new time, the new time will be
higher than the old one.

• It is impossible to guarantee that crystals in different

computers all run at exactly the same frequency.

• There is need therefore to view the global state

of the distributed system
 Clock Synchronization
Why timing is important in DS
– Each node has its own physical clock

– For many purposes, it is important that

machines agree on the same time.

– In DS it is often useful to establish a r/ship

between events at different processes.I.e
determine the relative ordering of events
occurring at different computers.
 Clock Synchronization
Time-stamping is done using two types of clocks.

– Logical clocks

– Physical clocks
 Physical Clocks
• Every computer contains a physical clock

• A clock (also called a timer) is an electronic device

that counts oscillations in a crystal at a particular
frequency and stores the result in a counter register.

• Clock can be programmed to generate interrupts at

regular intervals (e.g., at time interval required by a
CPU scheduler)
 Properties of Quartz Crystals
• Quartz generates an electrical
charge when pressure is
applied, as well as the reverse
• They can be cut in specific
ways that create resonators
(vibrators) of almost any
frequency that are practically
independent of temperature
variations
• The quartz crystals come in
various shapes and frequencies.

these are quartz crystals

you’re seeing…
 Physical Clocks
There two registers Associated with each crystal:-
1. A counter
2. Holding register
Each oscillation of the crystal decrements the
counter by one.
In this way it’s possible to program a timer
To generate an interrupt 60 times a second, or at
any other desired frequency.
 Physical Clocks
• Each interrupt is called one clock tick.

• At every clock tick, the interrupt service

procedure adds one to the time stored in
memory.

• In this way, the clock is kept up-date

Physical clocks: Drift rate, drift,clock skew
• It is impossible that the crystals in different computers
are run at exactly the same frequency.
• When a system has n computers all n crystals will run
at slightly different rates,
• Causing the clocks gradually to get out of synch and
give different values when read out.
• This difference in values is called clock skew.
• i.e: The difference between the times on two clocks |
Ci(t) – Cj(t)|
 Physical clocks: Drift rate,drift, clock skew

• clock drift rate: difference in precision between a

‘perfect’ reference clock and a physical clock.
• It is the difference per unit of time from some ideal
reference clock
- For quartz crystal clocks, typical drift rate is
about one second every 106 seconds =11.6
days
Physical clocks : problems encountered
– Drift: difference in the rate at which two clocks count the time.
– In practice the crystal based clocks used in computers will count
time at slightly different rates which means they will diverge(drift,
get out of sync) with respect to each other and with respect to real
time.

–Due to physical differences in the used oscillation

crystals, but also heat, humidity, voltage etc.

– accumulated drift can lead to significant skew

 Physical clocks
Time Service
• The purpose of a time service is to synchronize
the clock of a local computer with the clocks of
other computers on a network and to ensure that
all clocks agree with some real world clock.

• However, there are problems encountered by

global synchronization primitives and they
include:
 Physical clocks
problems encountered

– Network delay- The delay is unbounded. When a

server sends a message to a reference server, the
reference server returns reference time. The time
reference is made inaccurate by the variable time it
takes to send the time reference over the network

– Client and server processing delay- time taken to

process a message received is unpredictable.
Physical clocks: Atomic clock
• Atomic clock is a clock that was invented in
1948 and measures Time more accurately
by counting transitions of cesium 133 atom.

• Atomic clock is a device that uses as a

reference the exact frequency of the
microwave spectral line emitted by atoms of
the metallic element cesium.
Physical clocks:Atomic clocks
• There are about 50 laboratories around the world
have cesium 133 clocks.

• Periodically, each laboratory tells the bureaau

international de I’ heure(BIH) in paris how many
times its clock has ticked.
 International atomic Time(TAI).

• BIH averages to produce international

Atomic Time(TAI).

• This time tends to drift from the mean solar

day because the solar day is getting longer
all time.
 Leap second
• BIH adds adds leap seconds to TAI

• Whenever discrepancy between TAI And

solar time grows to 800ms.

• Solar day: takes into account the friction

as a result of the rotation and turbulence
Inside the earth’s crust.
 Computer Clock Synchronization

• Synchronized clocks is a requirement for some

applications in distributed systems.

– The total order that can be imposed with synchronized

clocks is sometimes needed by applications.

• It is not enough for individual clocks to run at

approximately the correct rate.

– A system of clocks will start drifting apart unless they are

periodically synchronized.
– With clocks skew, the question is then how to synchronize
all the clocks and achieve a single unambiguous time
standard.
Types of clock synchronization
• External clock synchronization

• Internal clock synchronization

 Physical clocks: External clock synchronization

• External clock synchronization requires maintaining

processor clocks within some given maximum deviation
from an external time reference, which keeps real time.

– E.g. if machine has a WWV receiver then the goal becomes keeping
all other machines synchronized to it (external synchronization)
 Physical clocks: Computer Clock Synchronization
• Internal clock synchronization requires that the
clocks of different processors be kept within some
minimum relative deviation of each other.

– Each machine keeps its own time and the goal is to keep all
the clocks synchronized as close as possible (internal
synchronization). Approximately synchronized clocks

– Two or more computers that are internally synchronized

are not necessarily externally synchronized, since they
may drift collectively from external form.

– Externally synchronized clocks are also internally

synchronized, though the reverse is not true
 Physical clocks: Computer Clock Synchronization

• It is possible that all clocks can be synchronized such

that Ci (t) is approximately equal to Cj (t) for all i,j
and t.(Approximately synchronized clocks)

• More precisely : Let | Ci(t) – Cj (t) | < E for all i,j;

where E is the synchronization error and E << 1.
• And t is time.

• Perfectly synchronized clocks have E=0;

Universal coordinated time (UTC)
• The correction of TAI by adding leap seconds
give rise to a time system based called universal
coordinated Time(UTC).

• To provide UTC to people who need precise time,

the National institute of standard Time(NIST)
operates a short wave radio station with calling
letters wwv from fort collins colorado.
Universal coordinated time (UTC)
• WWV is the call sign of NIST's Short wave radio
station located in fort collins, colarado.

• The main purpose of WWV is to continuously

disseminate of official UTC time signals

 UTC signals are then synchronized and broadcast

regularly from other land-based radio stations and
satellites covering many parts of the world
Universal coordinated time (UTC)
• There is propagation delay due to speed of light, distance from
broadcast source, atmospheric conditions, etc
– Received value is only accurate to 0.1–10 milliseconds

 Accuracy of the signal depends on the accuracy of the

source and its distance through the atmosphere

• if machine has a WWW receiver then the goal becomes

keeping all other machines synchronized to it. This is called
external synchronization.

• However, most workstations and PCs don’t have UTC receivers

 Physical clocks
Computer Clock Synchronization
The challenge is to device an algorithm to
ensure that the condition | Ci(t) – Cj (t) | < E
holds

– There is an E such that for all t, and any two

processes p and q, | Cp(t) – Cq (t) | <= E
 Clock Synchronization algorithms
Many algorithms have been proposed

– Cristian’s Algorithm
– Berkeley Algorithm
– Network Time Protocol (NTP)
Clock Synchronization: Christian's algorithm

• Assume one machine (the time server) has a

WWV receiver and all other machines are to
stay synchronized with it.

• Periodically, each machine sends a

message to the time server asking for the
current time.

• Time server responds with message

containing current time, CUTC.
Clock Synchronization: Cristian’s algorithm

Getting the current time from a time server

Clock Synchronization: Cristian’s algorithm

• client sets time to Tserver + Dtrans

• Tserver = server’s time
• Dtrans = transmission delay

• To improve precision the client make several

requests and take average of Tserver value
• To offset variations in time delay – client may
average over several requests

Disadvantage: The result is unpredictable due to network

propagation jitter
Clock Synchronization: Cristian’s algorithm

A major problem – the client clock is fast 

arriving value of CUTC will be smaller than
client’s current time, C.
– What to do?
• One needs to gradually slow down client clock
by adding less time per tick.
Clocks Synchronization: Berkeley Algorithm
a) The time daemon (Time server) asks all the other machines for their clock values.

b) The machines answer and the time daemon computes the average. It ignores
outliers

a) The time daemon tells everyone how to adjust their clock –either advance or slow
down.
Network Time Protocol (NTP)
• Uses a network of time servers to
synchronize all processors on a net.
• Time servers are connected by a
synchronization subnet tree.
• The root is adjusted directly .
• Each node synchronizes its children
nodes
Network Time Protocol (NTP)
• Time Servers provides time service on the
Internet
• Servers form a Hierarchical network.
– primary servers (100s) — connected directly to a time
source
– secondary servers (1000s) — connected to primary
servers in hierarchical fashion
• ns.cs.kent.edu runs a time server
– servers at higher levels are presumed to be more
accurate than at lower levels
Network Time Protocol (NTP)
Network Time Protocol (NTP)
• Every R seconds, each machine broadcasts its current time.

• The local machine collects all other broadcast time samples during
some time interval, S.
•
 Logical time and clocks
• Event ordering can be achieved without the
use of real-time clocks.
• Synchronization need not be absolute
(lamport)

– What matters in a DS is not that processes agree

on exactly what time it is but to be able to
establish r/ships between events at different
processes
– Is event a at p1 unrelated to event b at p2
– Was event a at p1 responsible for causing b at p2?
 Logical time and clocks
The happened before relation

• Lamport devised a synchronization mechanism based

on the “happened before” relation
• The happened before relation Assumptions
1. The system is composed of a system of processes

2. Each process in the DS consists of a sequence of events

3. The events of a process form a sequence where a occurs

before b in the sequence if a happens before b. The process
has total ordering

4. Sending or receiving a message is an event

5. Processes on the same computers communicate with each
other only by exchanging messages.
 Logical time and clocks
The happened before relation
The happened before relation is denoted
by the symbol “->”
The relation satisfies the following three
conditions
1. If a and b are events in the same process,
and a comes before b then a->b

2. If a is the sending of a message by one

process and b is the receipt of the same
message by another process, then a->b

3. If a->b and b-> then a->c

 Logical time and clocks
The happened before relation

• a->b means that it is possible for event a

to causally affect event b
• Two distinct events a and b are said to be
concurrent if a/-> b and b/->a
– These events are not ordered by -> as there is no
intervening message between them.

• In DS it is sometimes impossible to say that one

of two events occurred first

• The relation happened before is therefore only a

partial ordering of events in the system
 Logical time and clocks
Logical Clocks
• Lamport invented a mechanism by which
happened before relationship can be
captured without physical clocks, but
rather using logical clocks.

• A logical clock Ci is defined for each

process Pi, to be a function which assigns
a number to any event a in Pi
– A clock is just a way of assigning a number to
an event, where the number is thought of as
the time the event occurred.
 Logical time and clocks
Logical Clocks
• We now consider what it means for such a
system of clocks to be correct, known as
Correctness/clock condition

• The clock condition is satisfied if the

following two conditions hold:
– C1- if a and b are events in process pi and a
comes before b then Ci(a)< Ci(b)
– C2- If a is the sending of a message by process Pi
and b is the receipt of that message by process
Pj then Ci(a)<Cj(b)
 Logical time and clocks
Implementing Logical Clocks
• The logical clock is implemented as a local
variable in each process which contains a
value.

• The following two rule guarantees a correct

system of logical clocks.
– For each process Pj with logical clock Cj, Cj(b) is
the value contained in Cj during event b
– Process Pj increaments Cj between any two
successive events. This meets Condition one (c1)
 Logical time and clocks
Implementing Logical Clocks
• If event a is the sending of a message m by process Pi,
then the message is time stamped with the current
value of the clock and contains a timestamp Tm where
Tm=Ci(a)

• Upon receiving a message m, process Pj sets its clock Cj

greater than or equal to its present value and greater
than the maximum of the logical clock value and the
timestamp of the incoming message.
– The effect of this is to synchronize the local logical
clock of a process with the remote process that sent
the message.
 Logical time and clocks
Space time Diagram
• It is common to depict distributed computation
using an equivalent graphical representation called a
space-time diagram
• Horizontal lines represent execution of process,
with time processing from left to right
• An arrow from one process to another represents a
message being sent, with the sent event at the base
the arrow and the corresponding receive event at
the head of the arrow
• If a path can be traced from one event to another
along the the horizontal lines and arrows, then they
are causally related, otherwise they are concurrent.
Logical time and clocks
Space time Diagram