Chapter 5
Synchronization
Introduction
• In a centralized system, time is unambiguous. When a
process wants to know the time, it makes a system call
and the kernel tells it.
• If process A asks for the time. and then a little later
process B asks for the time, the value that B gets will be
higher than the value A got.
• Synchronization in Distributed Systems is much more
difficult than in uniprocessor systems
• Synchronization is important if we want to
– control access to a single, shared resource
– agree on the ordering of events
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
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.
A Note on Real Time
• Universal Coordinated Time (UTC):
basis of all modern civil timekeeping
• To provide UTC to people who need
precise time, the National Institute of
Standard Time (NIST) operates a
shortwave radio station with call letters
WWV from Fort Collins, Colorado.
Physical Clock Synchronization (1)
• In some systems (e.g., real-time systems),
the actual clock time is important.
• Under these circumstances, external
physical clocks are needed.
• For reasons of efficiency and
redundancy, multiple physical clocks are
generally considered desirable, which
yields two problems:
1 How do we synchronize them with real world clocks.
2 How do we synchronize the clocks with each other?
Measuring Time
• Traditionally time measured astronomically
– Transit of the sun (highest point in the sky)
– Solar day and solar second
• Problem: Earth’s rotation is slowing down
– Days get longer and longer
– 300 million years ago there were 400 days in the
year ;-)
• Modern way to measure time is atomic clock
– Based on transitions in Cesium-133 atom
– Still need to correct for Earth’s rotation
• Result: Universal Coordinated Time (UTC)
– UTC available via radio signal, telephone line,
satellite(GPS)
Synchronizing Clocks
• External synchronization
– Synchronize process’s clock with an
authoritative external reference clock S(t) by
limiting skew to a delay bound D > 0
|S(t) - Ci(t) | < D for all t
-E.g synchronization with a UTC source
• Internal synchronization
– Synchronize the local clocks within a
distributed system to disagree by not more
than a delay bound D > 0, without
necessarily achieving external
synchronization
- |Ci(t) - Cj(t)| < D for all i, j, t
Synchronization of Clocks: algorithms
• Cristian’s algorithm
• Berkeley algorithm
• Network time protocol (Internet)
Cristian’s Algorithm – External Synch
• External source S
• Denote clock value at process X by C(X)
• Periodically, a process P:
1. send message to S, requesting time
2. Receive message from S, containing time C(S)
3. Adjust C at P, should we set C(P) = C(S)?
• Reply takes time
• When P adjusts C(P) to C(S), C(S) > C(P)
Cristian’s Algorithm – External Synch
B T3
T2
T1 T4
• How to estimate machine A’s time offset relative to B?
Global Positioning System
• Computing a position in a two-dimensional space
Berkeley Algorithm – Internal Synch
• Internal: synchronize without access to an
external resource
|Ci(t) – Cj(t)| < D
Periodically,
S: send C(S) to each client P
P: calculate P = C(P) – C(S)
send P to S
S: receive all P’s
compute an average
send -P to client P
P: apply -P to C(P)
The Berkeley Algorithm
• Propagation time?
• Time server fails?
a) The time daemon asks all the other machines for their clock values
b) The machines answer
c) The time daemon tells everyone how to adjust their clock
Importance of Synchronized Clocks
• New H/W and S/W for synchronizing
clocks is easily available
• Nowadays, it is possible to keep millions
of clocks synchronized to within few
milliseconds of UTC
Event Ordering in Centralized
Systems
• A process makes a kernel call to get the time
• Process which tries to get the time later will
always get a higher (or equal) time value
no ambiguity in the order of events and their time
Example: Why Order Matters?
– Replicated accounts in New York(NY) and San Francisco(SF)
– Two updates occur at the same time
• Current balance: $1,000
• Update1: Add $100 at SF; Update2: Add interest of 1% at NY
• Whoops, inconsistent states!
Logical Clocks
• In physical clock, we have assumed that
clock synchronization is naturally related
to real time.
• But, it may be sufficient that the
processes in the DS agree on the
ordering in which certain events occur.
• Such “clocks” are referred to as Logical
Clocks.
• Lamport's timestamps
• Vector timestamps
Lamport Algorithm
• Clock synchronization does not have to be
exact
– Synchronization not needed if there is no
interaction between machines
– Synchronization only needed when machines
communicate
– i.e. must only agree on ordering of interacting
events
Lamport’s “Happens-Before” Partial Order
• Given two events e & e’, e < e’ if:
1. Same process: e <i e’, for some process Pi
2. Same message: e = send(m) and
e’=receive(m) for some message m
3. Transitivity: there is an event e* such that
e < e* and e* < e’
Concurrent Events
• Given two events e & e’:
• If neither e < e’ nor e’< e, then e || e’
Real Time
a b
P1
m1
c d
P2
m2
e f
P3
Lamport Logical Clocks
• Substitute synchronized clocks with a global
ordering of events
– ei < ej LC(ei) < LC(ej)
– LCi is a local clock: contains increasing values
• each process i has own LCi
– Increment LCi on each event occurrence
– within same process i, if ej occurs before ek
• LCi(ej) < LCi(ek)
– If es is a send event and er receives that send, then
• LCi(es) < LCj(er)
Lamport Algorithm
• Each process increments local clock between
any two successive events
• Message contains a timestamp
• Upon receiving a message, if received
timestamp is ahead, receiver fast forward its
clock to be one more than sending time
Lamport Algorithm (cont.)
• Timestamp
– Each event is given a timestamp t
– If es is a send message m from pi, then t=LCi(es)
– When pj receives m, set LCj value as follows
• If t < LCj, increment LCj by one
– Message regarded as next event on j
• If t ≥ LCj, set LCj to t+1
Lamport Algorithm (cont.)
a) Three processes, each with b) Lamport's algorithm
its own clock. The clocks run corrects the clocks
at different rates.
Lamport’s Algorithm Analysis (2)
• LC(ei) < LC(ej) ei < ej ?
• Claim: if LC(ei) < LC(ej), then it is not
necessarily true that ei < ej
a b Real Time
P1
1 2 m1
c d
P2
3 4
m2
e g f
P3
1 2 5
Total Ordering of Events
• Happens before is only a partial order
• Make the timestamp of an event e of
process Pi be:
(LC(e),i)
• (a,b) < (c,d) iff a < c, or a = c and b < d
Application: Totally-Ordered Multicasting
– Message is timestamped with sender’s logical
time
– Message is multicast (including sender itself)
– When message is received
• It is put into local queue
• Ordered according to timestamp
• Multicast acknowledgement
– Message is delivered to applications only when
• It is at head of queue
• It has been acknowledged by all involved processes
Application: Totally-Ordered Multicasting
• Update 1 is time-stamped and multicast. Added to local queues.
• Update 2 is time-stamped and multicast. Added to local queues.
• Acknowledgements for Update 2 sent/received. Update 2 can now be processed.
• Acknowledgements for Update 1 sent/received. Update 1 can now be processed.
• (Note: all queues are the same, as the timestamps have been used to ensure the
“happens-before” relation holds.)
Limitation of Lamport’s Algorithm
• ei < ej LC(ei) < LC(ej)
• However, LC(ei) < LC(ej) does not imply ei < ej
– for instance, (1,1) < (1,3), but events a and e are
concurrent
a b Real Time
P1
(1,1) (2,1) m1
c d
P2
(3,2) (4,2)
m2
e g f
P3
(1,3) (2,3) (5,3)
Vector Clocks (Vector Timestamps)
• In Lamport's logical clocks, if event a happened
before event b, then C (a) < C (b).
• But this does not necessarily imply that a
indeed happened before b.
• The problem is that Lamport clocks do not
capture causality.
• Causality can be captured by means of
vector clocks.
Vector Clocks Cont…
• A vector clock VC (a) assigned to an
event a has the property that if VC (a) <
VC (b) for some event b, then event a is
known to causally precede event b.
• Pi’s clock is a vector VTi[]
• VTi[i] = number of events Pi has stamped
• VTi[j] = what Pi thinks number of events Pj
has stamped (i j)
Vector Timestamps (cont.)
• Initialization
– the vector timestamp for each process is
initialized to (0,0,…,0)
• Local event
– when an event occurs on process Pi, VTi[i]
VTi[i] + 1
• e.g., on processor 3, (1,2,1,3) (1,2,2,3)
Vector Timestamps (cont.)
• Message passing
– when Pi sends a message to Pj, the message has
timestamp t[]=VTi[]
– when Pj receives the message, it sets VTj[k] to max
(VTj[k],t[k]), for k = 1, 2, …, N
• e.g., P2 receives a message with timestamp (3,2,4) and
P2’s timestamp is (3,4,3), then P2 adjusts its timestamp
to (3,4,4)
Comparing Vectors
• VT1 = VT2 iff VT1[i] = VT2[i] for all i
• VT1 VT2 iff VT1[i] VT2[i] for all i
• VT1 < VT2 iff VT1 VT2 & VT1 VT2
– for instance, (1, 2, 2) < (1, 3, 2)
Vector Timestamp Analysis
• Claim: e < e’ iff e.VT < e’.VT
a b [2,0,0] Real Time
P1
[1,0,0] m1
c d [2,2,0]
P2
[2,1,0] m2
e g f [2,2,3]
P3
[0,0,1] [0,0,2]
Application: Causally-Ordered Multicasting
• For ordered delivery of related messages
– Vi[i] is only incremented when sending
– When k gets a msg from j, with timestamp ts, the
msg is buffered until:
• 1: ts[j] = Vk[j] + 1
– (timestamp indicates this is the next msg that k is expecting
from j)
• 2: ts[i] ≤ Vk[i] for all i ≠ j
– (k has seen all msgs that were seen by j when j sent the msg)
Causally-Ordered Multicasting
P1 [0,0,0] P2 [0,0,0] P3 [0,0,0]
Post a
[1,0,0] a
c [1,0,0] e [1,0,0]
r: Reply a
[1,0,1]
d g
b [1,0,1]
[1,0,1]
Two messages:
message a from P1;
message r from P3 replying to message a;
Scenario1: at P2, message a arrives before the reply r
Causally-Ordered Multicasting (cont.)
P1 [0,0,0] P2 [0,0,0] P3 [0,0,0]
Post a
[1,0,0] a
d [1,0,0]
g [1,0,1] r: Reply a
b Buffered
[1,0,1] c
[1,0,0]
Deliver r
Scenario2: at P2, message a arrives after the reply r.
The reply is not delivered right away.
Ordered Communication
• Totally ordered multicast
– Use Lamport timestamps
• Causally ordered multicast
– Use vector timestamps
