SYNCHRONIZATION

IN DISTRIBUTED
SYSTEMS
 MODULE 4
Introduction – Clocks, events and process states – Synchronizing physical
clocks- Logical time and logical clocks – Global states – Coordination and
Agreement– Distributed mutual exclusion – Elections.
 INTRODUCTI
•
ON
In a centralized system: all processes reside on the
same system utilize the same clock.
• In a distributed system: like synchronize everyone’s
watch in the classroom.
• Time is monotonous
 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 Time Coordinate (UTC)
• UTC available via radio signal, telephone line, satellite (GPS)
 Global
GlobalTime is
Time
utilized to provide timestamps for
processes and data.
Physical clock: concerned with “People” time
Logical clock: concerned with relative time and
maintain logical consistency
 Physical Clocks
There are two aspects:

• Obtaining an accurate value for physical time

• Synchronizing the concept of time
physical
throughout the distributed system

• These can be implemented using centralized

algorithms or distributed algorithms
 Obtaining an Accurate
Physical Time
A physical time server is needed to access the current
time from a universal time coordinated (UTC).

Two sources for UTC:

WWW shortwave radiostation in Ft.Collins,Colorado.
Geostationary operational Environmental satellites
 Synchronizing Physical
Time
• The difference in time between two clocks due to
drifting is defined as clock skew.
• As long as any and every two clocks differ by a value
less than the maximum skew value, the time service is
considered to be maintaining synchronization.
 Skew between
computer
clocks in a distributed
system
How to synchronize two clocks in
A
and B?
• The information necessary to read the value must be
communicated across the network to location B.
• B’s clock value must be read.
• B’s clock value is communicated back to location A.
• B’s clock value is adjusted to reflect the time
necessary to travel across the network.
• B’s clock value is compared to A’s clock value.
 Centralized Physical Time
Services
Broadcast Based

Request Driven
 Broadcast Based – first
approach
The centralized time server’s action:
The physical time service broadcasts periodically the current time to members
of the distributed systems.

The participants’ action:

 If a given participant’s clock is ahead of the time server’s clock, the
participant slows down its clock so that it will continually move closer to the

accurate time.
If a participant’s clock is behind the time server’s clock, the participant
moves its clock forward. Alternatives do include gradually speeding up the
clock.
 Location A Time server
Current time Current time=740
= 720 Delay of 10 Broadcast based

Location A
Current time=720
Adjusted current time=750
New current time=750
 Location A Time Server Location B
1 1
Current time=740
2 Adjusted location A 2 Current time=732
Current time=720 Delay=6
Delay=10 =730
Adjusted location B Slow clock down to
4 =738 5 accommodate 2
Move forward=6
Average and the new
current time=736

1. Current time = 740

2. My current time = 720
3. My current time = 732
4. Adjust forward = 6
5. Adjust slowdown to accommodate 2
 Location A Timer Server
Current time=730 Request for
current time Current time=740

Current time=740
Adjusted time=750 Delay=10

New current time=750

 Distributed Physical Time
Service
Each location broadcasts its current time at predefined set
intervals.
Once a location has broadcast its time, it starts a timer. It then
collects time messages that it receives.
 Each time message that arrives is stamped with the local
current time.
This process continues until the timer expires.
Upon the expiration of the timer, each message is adjusted to
reflect the network delay time estimated for the message
source.

Calculate the average of all messages

Adjusted received times

720
724
726
718
722
723
Delete the times that are above the threshold and then
average the rest.

Adjusted received times

760 X
724 The numbers besides X are deleted.
726 The rest are averaged.
718
702 X
723
Discard the highest x and the lowest x values and then
average

Adjusted received times

760 X
724
726
718
702 X
723
703 X
765 X
 Logical
Clocks
Why Logical Clocks?
•It is difficult to utilize physical clocks to order events
uniquely in distributed systems.
• The essence of logical clocks is based on the happened-
before relationship presented by Lamport.
 Happen-Before
• Relationship
If two events, a and b, occurred at the same process,
they occurred in the order of which they were
observed. That is, a > b.
• If a sends a message to b, then a > b. That is, you
cannot receive something before it is sent. This
relationship holds regardless of where events a and
b occur.

• The happen-before relationship is transitive. If a happens before b and b

happens before c, then a happens before c. That is, if a > b and b > c,
then a > c.
 Logical
Ordering
• If T(a) is the timestamp for event a, the following relationships must hold in a
distributed system utilizing logical ordering.

• If two events, a and b, occurred at the same process,

they occurred in the order of which they were
observed. That is T(a) > T(b).
• If a sends a message to b, then T(a) > T(b).
• If a happens before b and b happens before c, T(a)
> T(b), T(b) > T(c), and T(a) > T(c).
 E F
Process 3

C D
Process 2

A B
Process 1

A>B>C>D>F E
 Lamport’s
•
Algorithm
Each process increments its clock counter between
every two consecutive events.
• If a sends a message to b, then the message must
include T(a). Upon receiving a and T(a), the
receiving process must set its clock to the greater of
[T(a)+d, Current Clock]. That is, if the recipient’s
clock is behind, it must be advanced to preserve the
happen-before relationship. Usually d=1.
 E(1)
F(5)
Process 3

C(3) D(4)
Process 2

A(1) B(2)
Process 1
 E(1.3)
F(5.3)
Process 3

C(3.2) D(4.2)
Process 2

A(1.1) B(2.1)
Process 1

A>E>B>C>D>F
 Mutual
• In
Exclusion
single-processor systems, critical regions are
protected using semaphores, monitors, and similar
constructs.
• In distributed systems, since there is no shared memory,
these methods cannot be used.
Entry section
{
P1;
}
exit
 A Centralized Algorithm
coordinator
process Request
Grant

Enter crical Release

section

Exit
Advantages: It is fair, easy to
implement, and requires only three messages
per use of a critical region (request, grant, release).
Disadvantages: single point of failure.
OK OK
REQ REQ

REQ REQ
 Election
Algorithm
The bully algorithm
When a process notices that the coordinator is no longer
responding to requests, it initiates an election. A
process, P, holds an election as follows:
P sends an ELECTION message to all processes with
higher numbers.
If no one responds, P wins the election and becomes
coordinator.
If one of the higher-ups answers, it takes over. P’s job is
done.
 1 1
7 7 2
2
Election
6 6 3
Election
3 5
5
4 4
1 1
7 2 7 2
Coordinator
6 Ok 3 6 3
5 4 5 4
A Ring Algorithm

234561
1
2 6
2
7

3
23
23456 6

4
5

2345 234
 Atomic
Transactions
• All the synchronization techniques we have
studied so far are essentially low level, like semaphores.
• What we would really like is a much higher-level
abstraction such as atomic transaction.
 For
Example
Atomic bank transactions:
•Withdraw(amount, account1)
•Deposit(amount, account2)
 Stable
• Storage
Stable storage is designed to survive anything except
major calamities such as floods and earthquakes.
• Stable storage can be implemented with a pair of
ordinary disks.
• Stable storage is well suited to applications that require a
high degree of fault tolerance, such as atomic
transactions.
 Transaction
Primitives
BEGIN_TRANSACTION: Mark the start of a transaction.
END_TRANSACTION: Terminate the transaction and try to commit.
ABORT_TRANSACTION: Kill the transaction; restore the old values.
READ: Read data from a file (or other object).
WRITE: Write data to a file (or other object).

 For example,
 BEGIN_TRANSACTION
reserve Austin-Houston;
reserve Houston-Los Angeles;
reserve Los Angeles-Seatle;
 END_TRANSCATION
 Properties of
Transactions
Atomic: To the outside world, the transaction happens
indivisibly.
Consistent: The transaction does not violate system
invariants.
Isolated: Concurrent transactions do not interfere with
each other.
Durable: Once a transaction commits, the changes are
permanent.