5) Concurrency Control

Concurrency Control
 Clock synchronization
 Logical clocks and global state
 Election Algorithms
1
Clock Synchronization: Introduction
• We need to measure time accurately:

• to know the time an event occurred at a computer
• to do this we need to synchronize its clock with an authoritative external
clock
• Algorithms for clock synchronization are useful for

• concurrency control based on timestamp ordering
• authenticity of requests e.g. in Kerberos
• There is no global clock in a distributed system

• Logical time is an alternative
• It gives ordering of events - also useful for consistency of replicated data
2
Clock Synchronization: Sources of Accurate Timing Signals
 International Atomic Time is based on very accurate physical

clocks (drift rate 10-13).
 Coordinated Universal Time (UTC) is an international standard for
time keeping.
 It is broadcast from radio stations on land and satellite (e.g. GPS).
 Computers with receivers can synchronize their clocks with these
timing signals.
 Signals from land-based stations are accurate to about 0.1-10
millisecond.
 Signals from GPS are accurate to about 1 microsecond.
3
Clock Synchronization
 Difficulties in clock synchronization in DS
– Not all sites have direct access to accurate time source
such as a GPS receivers due to the cost.
– Sites has to synchronize their local clocks with those
have more accurate time.
– Synchronization needs to be done periodically due to
clock drift: rate is change in the offset (difference in
reading) between the clock and a normal perfect
reference clock per unit of time measured (about 10 -6 or
1 sec. in 11.6 days).
 If a site’s clock is ahead of the reference (time
server) to which it synchronizes to, it cannot be
simply set back.
4
Clock Synchronization
 For process pi
– Ci(t) – software clock
– Hi(t) – Hardware clock, I.e., the time given by hardware clock
Thus: Ci(t) = H(t)+ 
 Various notions of correctness for clocks have been suggested.
 It is common to define a hardware clock H to be correct if its
drifts fall within a known bound  > 0 (e.g. for real-time t’ and t,
t’>t).
 The error in measuring the interval between real times t’ and t,
t’>t) is bounded:
(1-  )(t’-t) ≤ H(t’) – H(t) ≤ (1+ )(t’-t)
5
External and Internal Clock Synchronization
 External synchronization
– A computer’s clock Ci is synchronized with an external authoritative time
source S, so that:
– |S(t) - Ci(t)| < D for i = 1, 2, … N over an interval, I of real time
– The clocks Ci are accurate to within the bound D.
 Internal synchronization
– The clocks of a pair of computers are synchronized with one another so
that:
– | Ci(t) - Cj(t)| < D for i = 1, 2, … N over an interval, I of real time
– The clocks Ci and Cj agree within the bound D.
 Internally synchronized clocks are not necessarily externally
synchronized, as they may drift collectively.
 if the set of processes P is synchronized externally within a bound
D, it is also internally synchronized with a bound of 2D.
6
Clock Synchronization: Cristian Algorithm
 Client C requests time in Request message sent to time server S,
then it receives time value t in message CUTC from S. t is the current
time in S before sending back CUTC to C.
 Let Ttrans be time taken for CUTC message from S to C, then C should
set its time to t + Ttrans .
 Ttrans can be variant. You may say: Ttrans = min+x, x ≥ 0 and min = time
of message transmission if no interference of other process and no
other messages, but x is unknown!
 Solution: (1) Record total round trip time as Tround (between sending
Request and receiving CUTC,, i.e., T1-T0) (2) If the time received in
Request message is t, then C can estimate its time as: t + Tround/2.
7
Clock Synchronization: Cristian Algorithm
 Keep in mind: C’s time is t + Tround/2.

 Let the minimum transmission time be min, and min is known.
 Therefore, t’ (the time in S when C receives CUTC ) lies in the
range [t+min, t+Tround  min]
t+ Tround min  (t+min) = Tround 2min
The accuracy for this time adjustment is
(Tround/2min)
 Problem: single-server failure.
 Solution: providing group synchronization time servers.
8
Clock Synchronization: Berkeley Algorithm
 In Berkeley UNIX, one of a group sites (computers) is chosen as
coordinator, (master or time server).
(1) The master (actually a time daemon in the master) periodically polls the
other sites (slaves) to ask what time it is there, by telling its own time (the time in
master) to these slaves.
(2) The slaves response with how far ahead or behind the time daemon they
are, that is, the difference between its time and the time in master.
(3) Based on the replies from the slaves, the master averages the time obtained
(including its own).
(4) The master sends time rate adjust value (+ or -) to slaves, requesting them
to adjust their time rate.
9
The Berkeley Algorithm: An Example
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
10
Clock Synchronization: Network Time Protocol
(NTP)
 NTP is used in the Internet. Time servers are arranged in levels

called strata. NTP intends to:
– provide a service enabling clients in Internet to be
synchronized accurately to UTC.
– provide reliable service to losses of connectivity.
– enable clients to resynchronize sufficiently and frequently.
– provide protection against interference with the time service.
11
Clock Synchronization: Network Time
Protocol
 Synchronization clock: Network Time Protocol (NTP)
 Stratum 1: Primary server (PS) sync directly with UTC sources.
 Stratum 2: Secondary servers (SS) sync directly to PS.
 Stratum 3: Lowest servers (LS) execute in user sites sync with SS.
 Accuracy: the number of levers (strata).
2 2
3 3 3
12
Clock Synchronization: Network Time
Protocol
 Multiple servers provide for redundancies and hence availability

of time sources and fault-tolerance.
 NTP synchronizes with one another in one of three modes:
– Multicast: Used on LAN. One or more servers periodically
broadcast the time to servers running in workstations which
set their clocks assuming a small delay. Accuracy is low.
– Procedure-call: Similar to Cristian’s method. Workstations ask
the server the time. Accuracy is higher than multicast.
– Symmetric mode: Used by high level to achieve highest
accuracy. A pair of servers exchange messages bearing
timing information.
13
Logical Time and Logical Clock
 Refer to Class Notes
14
Global State
 It is often useful to know the global state in which a

distributed system is currently residing, e.g., to detect the
termination of a distributed computation, or deadlock etc.
 Global state of a DS: The local state of each process, and
the messages that are currently in transit.
 Distributed snapshot: reflects a (consistent global) state in
which the DS might have been. It is not desirable that a
snapshot contains the recording of messages that have been
received but never sent.
 Cut: A graphical representation of global state, as shown in
the next slide.
15
Global State (1)
a) A consistent cut
b) An inconsistent cut
16
Global State: Algorithm for Taking Snapshot I
 Assume that the DS can be represented as a collection of

processes connected to each other through unidirectional
point-to-point communication channels (e.g., TCP
connection).
 Any initiating process, say P, may start by recording its own
local state; then it sends a marker along each of its outgoing
channels;
 When a process Q receives a marker from an incoming
channel C,
* If Q has not saved its local state, it first saves the state, then
sends a marker along each of its own outgoing channels.
17
Global State: Algorithm for Taking Snapshot II
* If Q has recorded the local state, it records the state of

channel C: the sequence of messages that have been
received by Q since the last time Q recorded its local state,
and before it received the marker.
 When a process has received a marker along each of its
incoming channels, and processed each one, its recorded
local state and state of each channel are collected and sent
to process P.
 Because any process can initiate the algorithm, several
snapshots can be constructed at the same time. To identify
different processes of snapshot construction, a marker can
be tagged with identifier (even version) of process that
initiates the snapshot.
18
Global State (2)
a) Organization of a process and channels for a distributed

snapshot
19
Global State (3)
b) Process Q receives a marker for the first time and records its local
state
c) Q records all incoming message
d) Q receives a marker for its incoming channel and finishes recording
the state of the incoming channel
20
Global State: Algorithm for Termination Detection I
 The termination of a distributed computation can be detected

using the algorithm of taking a snapshot.
 A snapshot may show a global state in which message are
still in transit, which means the distributed computation has
not terminated.
 The termination detection algorithm is a simple modification
of the snapshot algorithm. Assume that a process Q receives
the marker from process P, requesting a snapshot for the first
time, then P is said to be the predecessor of Q.
 When a process Q finishes its part of the snapshot, it either
returns DONE or CONTINUE message to its predecessor:
21
Global State: Algorithm for Termination Detection II
* DONE: all of Q’s successors have returned a DONE

message; and Q has not received any message between the
point it recorded its state and the point it had received the
marker along each of its incoming channel;
* CONTINUE: In all other cases.
 When the original initiator of the snapshot, say P, receives
only the DONE messages, it concludes that the distributed
computation has terminated; Otherwise, P initiates another
snapshot, and continues to do so until only DONE message
are eventually returned.
22

5) Concurrency Control

Uploaded by

Copyright:

Available Formats

5) Concurrency Control

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

5) Concurrency Control

Uploaded by

Copyright:

Available Formats

Concurrency Control

• We need to measure time accurately:

• Algorithms for clock synchronization are useful for

• There is no global clock in a distributed system

 International Atomic Time is based on very accurate physical

 Keep in mind: C’s time is t + Tround/2.

 NTP is used in the Internet. Time servers are arranged in levels

 Multiple servers provide for redundancies and hence availability

 Refer to Class Notes

 It is often useful to know the global state in which a

 Assume that the DS can be represented as a collection of

* If Q has recorded the local state, it records the state of

a) Organization of a process and channels for a distributed

 The termination of a distributed computation can be detected

* DONE: all of Q’s successors have returned a DONE

You might also like