Clock Synchronization

Just use as a supplement of my lecture.

Detail explanations of algorithms and examples are in the class lectures
Introduction
• Synchronization: coordination of actions between processes.
• Centralized systems: primarily accomplished through shared memory;
• Semaphores
• All events are timed by the same clock
• Synchronization in distributed systems is harder
• No shared memory, no common clock
Physical Clocks
• Physical clock example: counter + holding register + oscillating
quartz crystal
• The counter is decremented at each oscillation
• Counter interrupts when it reaches zero
• Reloads from the holding register
• Interrupt = clock tick
• Software clock: counts interrupts
• This value represents number of seconds since some predetermined
time (Jan 1, 1970 for UNIX systems; beginning of the Gregorian
calendar for Microsoft)
• Can be converted to normal clock times
• The same technology is used in most
clocks, watches, cell phones
Clock Skew
• In a distributed system each computer has its own
clock; each crystal will oscillate at slightly different
rate.
• Gradually, clocks are no longer the same.
• Clock skew: the difference between the times on two
different clocks
• Clock drift: the difference between a clock and actual
time
Various Ways of Measuring Time*
• The sun
• Mean solar second – gradually getting longer as earth’s
rotation slows.
• International Atomic Time (TAI)
• Atomic clocks are based on transitions of the cesium atom
• Atomic second = value of solar second at some fixed time
(no longer accurate)
• Universal Coordinated Time (UTC)
• Based on TAI seconds, but more accurately reflects sun
time (inserts leap seconds to synchronize atomic second
with solar second)
Getting the Correct (UTC) Time*
• WWV radio station or similar stations in other countries (accurate to
+/- 10 msec)
• UTC services provided by earth satellites (accurate to .5 msec)
• GPS (Global Positioning System) (accurate to 20-35 nanoseconds)
Clock Synchronization Algorithms
• Network Time Protocol (NTP):
• Objective: keeps clocks in a system synchronized to UTC time
(1-50 msec accuracy);
• State of the art
• The Berkeley Algorithm:
• Objective: to keep all clocks in a system synchronized to each
other (internal synchronization)
• Uses active time servers that poll machines periodically
• Reference broadcast synchronization (RBS) (not go in
detail)
• Objective: to keep all clocks in a wireless system synchronized
to each other
Logical Clocks
• Observation: if two processes (running on separate processors) do
not interact, it doesn’t matter if their clocks are not synchronized.
• Observation: When processes do interact, they are usually interested
in event order, instead of exact event time.
• Conclusion: Logical clocks are sufficient for many applications
Formalization
• The distributed system consists of n processes, p1, p2, …pn (e.g, a MPI
group)
• Each pi executes on a separate processor
• No shared memory
• Each pi has a state si
• Process execution: a sequence of events
• Changes to the local state
• Message Send or Receive
Two Versions
• Lamport’s logical clocks: Can be used to determine an absolute
ordering among a set of events although the order doesn’t
necessarily reflect causal relations between events.
• Vector logical clocks: can capture the causal relationships between
events.
• Causality: one event has an effect on another.
Lamport’s Logical Time
• Causality in this sense is defined as a “happens-before”
relation between events in a process.
• "Events" are defined by the application. The granularity
may be as coarse as a procedure or as fine-grained as a
single instruction.
• Leslie Lamport defined the happens-before relation.
Happens Before Relation (a → b)
• a → b: 3 rules for determining (pp. 244-5)
• in the same [sequential] process,
• send, receive in different processes, (messages)
• transitivity: if a → b and b → c, then a → c
• If a → b, then a and b are causally related; i.e., event a potentially has
a causal effect on event b.
Concurrent Events
• Happens-before defines a partial order of events in a distributed
system.
• Some events can’t be placed in a happens-before order
• a and b are concurrent (a || b) if
!(a → b) and !(b → a).
• If a and b aren’t connected by the happened-before relation, there’s
no way one could affect the other.
Logical Clocks
• Needed: method to assign a “timestamp” to event a (call it C(a)).
• Define a logical clock (event counter), Ci, at each process (processor)
Pi.
• When an event a occurs, its timestamp ts(a) = C(a), the local logical
clock value at the time the event takes place.
• The clocks must obey certain rules to reflect the happens-before
relation.
Correctness Conditions
• If a and b are in the same process, and
a → b then C (a) < C (b)
• If a is the event of sending a message from Pi, and b is
the event of receiving the message by Pj, then (it
should be true that) Ci (a) < Cj (b).
• The value of Ci must be increasing (time doesn’t go
backward).
• Corollary: any clock corrections must be made by adding a
positive number to a time.
Implementation Rules
Lamport’s Logical Clocks (2)
Event a: P1 sends m1 Event c: P3
to P2 at t = 6, sends m3 to P2
Event b: P2 receives at t = 60
m1 at t = 16. Event d: P2
If C(a) is the time m1 receives m3 at t
was sent, and C(b) is = 56
the time m1 is Do C(c) and C(d)
received, do C(a) and satisfy the
C(b) satisfy the conditions?
correctness conditions
?

(a) Three processes, each with its own clock. The clocks “run”
at different rates.
Lamport’s Logical Clocks (3)
Here, Lamport’s
algorithm has been
used to “synchronize”
the clocks: P2 has
adjusted its clock from
56 to 6.
Note that next events
reflect the new value
of the clock.

(b) Lamport’s algorithm corrects the clocks.

A Total Ordering Rule
(does not guarantee causality)

• Previous example: many causally ordered sequences of events.

• None include all events in the system
• A total ordering of events can be obtained if we ensure that no two
events happen at the same “time” (have same timestamp).
• Why? So all processes can agree on an unambiguous order for system
events.
• No causal ordering implied
A Total Ordering Rule
(does not guarantee causality)
• How?
• One way: Attach process number to low-order end
of time, separated by decimal point; e.g.,
• event at time 40 in process P1 is 40.1
• event at time 40 in process P2 is 40.2
• Arbitrarily but deterministically we have chosen to
order P1 before P2 (write P1 => P2)
• Now every event in the system has a unique
timestamp
Application of Lamport Clocks: Total Order
Multicast
• Consider a banking database, replicated across
several sites.
• Queries are processed originally at the geographically
closest replica but other replicas are updated.
• We need to be able to guarantee that DB updates are
seen in the same order everywhere.
Totally Ordered Multicast Example

Update 1: Process 1 at Site A adds $100 to an

account, (initial value = $1000)
Update 2: Process 2 at Site B increments the
account by 1%
Without synchronization,
it’s possible that
replica 1 = $1111,
replica 2 = $1110
Totally Ordered Multicast Example

• Message 1: add $100.00

Message 2: increment account by 1%
• The replica that sees the messages in the order m1,
m2 will have a final balance of $1111
• The replica that sees the messages in the order m2,
m1 will have a final balance of $1110
The Problem
• Site 1 has final account balance of $1,111 after both
transactions complete and Site 2 has final balance of
$1,110.
• Which is “right”? Either, from the standpoint of
consistency.
• Problem: lack of consistency.
• Both values should be the same
• Solution: make sure both sites see/process all
messages in the same order.
Assumptions
• Updates are multicast to all sites, including
(conceptually) the sender
• No messages are lost
• All messages from a single sender arrive at each
replica in the order in which they were sent; i.e., if
send(mi) → send(mj) then every site that receives
both messages should receive mi before mj.
• Messages are time-stamped with Lamport clock
values (the totally ordered version).
Implementation
• When a process receives a message, put it in a local
message queue, ordered by timestamp.
• Multicast an acknowledgement to all sites
• Each ack has a timestamp larger than the timestamp
on the message it acknowledges
• The message queue at each site will eventually be in
the same order
Implementation
• Deliver a message to the application only when the following
conditions are true:
• The message is at the head of the queue
• The message has been acknowledged by all other receivers. This guarantees
that no update messages with earlier timestamps are still in transit.
• Acknowledgements are deleted when the message they acknowledge
is processed.
• Since all queues have the same order, all sites process the messages
in the same order.
Importance
• Maintaining consistent replicas is an important feature in distributed
systems
• Totally ordered multicast is a way to implement it correctly.
Causality
• Happens-before relation reflects causality:
• Event a may causally affect event b if a → b
• Events a and b are causally related if either
a → b or b → a.
• If neither of the above relations hold, then there is no causal relation
between a & b. We say that
a || b (a and b are concurrent)
• The total ordering relation doesn’t reflect causality.
 Vector Clock Rationale
• Lamport clocks limitation, for a & b on different
processors:
• If (a→b) then C(a) < C(b) but
• If C(a) < C(b) then we only know that either (a→b) or (a || b),
i.e., b a
• In other words, you cannot look at the clock values of
events on two different processors and decide which
one “happens before”.
• Lamport clocks do not capture causality
Lamport’s Logical Clocks (3)
Suppose we add a message to the
m2 ’ scenario in Fig. 6.12(b).
• Tsnd(m1) < Tsnd(m3’).
(6) < (32)
• Does this mean
m3 ’
send(m1) → send(m3’)?
But …
• Tsnd(m1) < Tsnd(m2’).
(6) < (10)
• Does this mean
send(m1) → send(m2)?
Vector Clocks – How They Work
• Each processor keeps a vector of values, instead of a
single value.
• VCi is the clock at process i; it has a component for
each process in the system.
• VCi[i] corresponds to Pi‘s local “time”.
• VCi[j] represents Pi‘s knowledge of the “time” at Pj (the # of
events that Pi knows about at Pj)
• Each processor knows its own “time” exactly, and
updates the values of other processors’ clocks based
on timestamps received in messages.
Implementation Rules
Example
Happened Before/Causally Related Events - Vector
Clock Definition
• a → b iff ts(a) < ts(b)
(a happens before b iff the timestamp of a is less than the timestamp
of b)
• Events a and b are causally related if
• ts(a) < ts(b) or
• ts(b) < ts(a) (in other words, a → b or b → a )
• Otherwise, we say the events are concurrent.
• Any pair of events that satisfy the vector clock definition of happens-
before will also satisfy the Lamport definition, and vice-versa.
Comparing Vector Timestamps
• Less than: ts(a) < ts(b) iff at least one component of
ts(a) is strictly less than the corresponding component
of ts(b) and all other components of ts(a) are either
less than or equal to the corresponding component in
ts(b).
• Example:
(3,3,5) < (3,4,5), (3, 3, 3) ═ (3, 3, 3),
(3,3,5) > (3,2,4), (3, 3 ,5) | | (4,2,5).
Example
Causal Ordering of Messages
An Application of Vector Clocks
• Premise: Deliver a message only if messages that causally precede it
have already been received
• i.e., if send(m1) → send(m2), then it should be true that receive(m1) →
receive(m2) at each site.
• If messages are not related (send(m1) || send(m2)), delivery order is not of
interest.
Compare to Total Order
• Totally ordered multicast (TOM) is, in a way, stronger (more inclusive)
than causal ordering (COM).
• TOM orders all messages, not just those that are causally related.
• “Weaker” COM is often what is needed – it ignores messages that aren’t
relevant.
Review
• Physical clocks: hard to keep synchronized
• Logical clocks: can provide some notion of relative
event occurrence
• Lamport’s logical time
• happened-before relation defines causal relations
• Lamport’s logical clocks – don’t capture causality
• total ordering relation is useful
• use in establishing totally ordered multicast as well as other
applications
• Vector clocks
• Unlike Lamport clocks, vector clocks capture causality
• Have a component for each process in the system