HARAMAYA UNIVERSITY

COLLEGE OF COMPUTING AND INFORMATICS

DEPARTMENT OF INFORMATION TECHNOLOGY

DISTRIBUTED SYSTEMS

CHAPTER 6: Synchronization in Distributed System

Compiled By: Gizachew B.

2
Contents

 Introduction

 Clock Synchronization

 Physical Clocks

 Clock Synchronization Algorithms

 Logical Clocks

 Mutual Exclusion

 Election Algorithms
3 Introduction (1)

 Most of us use distributed systems on a daily basis, and for good reason; the stability, fault tolerance and scalability they

offer give us the flexibility to make more robust, high-performance applications.

 However, distributed systems come with their own set of unique challenges, including synchronizing data and conflicts.

 Synchronization is coordination of actions between processes.

 Processes need to cooperate or synchronize for mutual understanding and event ordering.
4 Clock Synchronization (1)

 In distributed systems the nodes are communicating with each other using message

passing.

 Many real-time applications such as banking systems, reservation systems that are

implemented on distributed systems, it is important to execute each

transaction/event in an ordered manner.

 Ordering of events is essential for proper allocation of available resources and

mutual allocation.

 This can be implemented using clock synchronization.

 Whenever massage is sent by a node the sender node timestamps (attaches the time

by which this message was sent according to its own clock) the message so that the

message will be ordered correct.

5 Clock Synchronization (2)

 If all clocks read the same what ever event happened in the distributed system, (even though all nodes have their

own clock) its sequence can be agreed by all nodes in the distributed system.

 Clock synchronization in its perfect sense is meant to make all clocks in a distributed system to read same with no

difference among them (skew zero).

 It is a mechanism to synchronize the time of all computers in distributed system environments.

 Clock synchronization deals with understanding the temporal ordering of events produced by concurrent processes.

 It is useful for synchronizing senders and receivers of messages, controlling joint activity, and the serializing

concurrent access to shared objects.

 The goal is that multiple unrelated processes running on different machines should be in agreement with and be

able to make consistent decisions about the ordering of events in a system.

6 Clock Synchronization (3)

 Another aspect of clock synchronization deals with synchronizing time-of-day clocks among groups of machines.

 In this case, we want to ensure that all machines can report the same time, regardless of how imprecise their clocks may be or

what the network latencies are between the machines.

 Synchronization in distributed systems is often much more difficult compared to synchronization in centralized uniprocessor or

multiprocessor systems.

 In a centralized system where there is a dedicated master node that manage the distributed system, time is unambiguous because

it uses shared memory and processor.

 In shared memory of centralized system, event ordering is clear because all events are timed by the same clock.

 In such systems, when a process (node) wants to know the time, it makes a system call and the kernel tells it.

 In a distributed system, achieving agreement on time among the nodes in the distributed system is essential.

 Synchronization in distributed system used separated memory and processors. So, it is hard because all nodes have their own

clock.
7 Clock Synchronization (4)

Therefore, the need to have Synchronized clock in distributed system is:

1) To have accurate notion of global agreed upon ordering of events (an event is often an arrival or sending of message by

particular member of the distributed system)

2) To establish agreed up on access order to distributed resource (if for example the distributed server employs FCFS (First

come first served) algorithm to assign resources like printer or reading a shared file)

3) To remove inconsistent contents (varying state) for specific resource that could arise due to unsynchronized time and

many more.

 In computers, clock synchronization performs based on the physical clock of a computer.

 Before going into detail about synchronization, first we need to understand how physical clock structure of

computer is implemented and how it works.

8 Clock Synchronization…………. Physical Clocks (1)
 Every computer contains a physical clock.

 Clock is an electronics device that count oscillations in a crystal at a particular frequencies.

 Count is typically divided and stored in a counter register

 Clock can be programmed to generate interrupt at regular intervals and can be used to timestamp an event on a

computer.

 Each computer consists of quartz crystal that oscillates at a predictable frequency when pressed.

 A counter register keeps track of oscillation and decrements by one for every oscillation.

 When it reaches to zero, an interrupt is generated and counter is reloaded from the holding register.

 The value of holding register is decided based on the frequency of oscillation and the number of interrupts can be

controlled.

 The holding register value is chosen to be 60 clock ticks per second.

9 Clock Synchronization…………. Physical Clocks (2)

 There may be differences in crystal oscillation, leads to the clock running at d/t rates, which is known as clock drift.

 This difference in oscillation period may be small but difference accumulates over many oscillations hence computer

clock drifts from real time clock.

 For quartz crystal, drift rate is 10-6 seconds or 1 second for every 11.6 days.

 The difference between time values of any two clocks is called their skew

 The atomic clock is used for a standard real time known as International Atomic Time.

 Universal Coordinated Time (UTC) is based on atomic time.

 Clock synchronization in distributed system relies on this standard external clock time value for synchronization.

 UTC time is used as a reference clock time for physical clocks in the system.
10 Clock Synchronization…………. Physical Clocks (3)

There are two ways of synchronization:

1. External clock synchronization: External clock time is used as a reference time for other clocks in the

system and computer set their time accordingly.

2. Internal clock synchronization: Each node shares their physical clock time value with other nodes and set

their new clock value accordingly for clock synchronization.

 Computers have the same problem: a quartz crystal on one computer will oscillate at a slightly different frequency than on

another computer, causing the clocks to tick at different rates.

 The phenomenon of clocks ticking at different rates, creating a ever widening gap in perceived time is known as clock drift.

 The difference between two clocks at any point in time is called clock skew and is due to both clock drift and the possibility

that the clocks may have been set differently on different machines.
11 Clock Synchronization…………. Physical Clocks (4)

 Figure 1. illustrates this phenomenon with two

clocks, A and B, where clock B runs slightly faster

than clock A by approximately 2 seconds per hour.

 This is the clock drift of B relative to A.

 At one point in time (5 seconds past five o'clock

according to A's clock), the difference in time

between the two clocks is approximately 4 seconds.

 This is the clock skew at that particular time.

Figure 1. Clock drift and Clock skew
12 Clock Synchronization…………. Algorithms (1)

 Several techniques and algorithms are used to attempt the synchronization of physical clock in distributed system.

 Universal Coordinated Time (UTC)

 Christian’s Algorithm

 Berkeley Algorithm
13 Clock Synchronization…………. Algorithms (2)

Universal Coordinated Time (UTC)

 Universal coordinated time is international time standard.

 All computers are generally synchronized to a standard time called UTC.

 UTC is the primary time standard by which the world regulates clock and time.

 It is available via radio signals, telephone line, satellite (GPS).

 It is broadcasted via the satellites.

 UTC broadcasting service provides an accuracy of 0.5 msec.

 Computer server and online services with UTC receives can be synchronized by satellite broadcasts.

 Many popular synchronization protocols in distributed system use UTC as a reference time to synchronize clocks of

computers.
14 Clock Synchronization…………. Algorithms (3)

Problem: Sometimes we simply need the exact time not just an ordering.

Solution: Universal Coordinated Time (UTC).

 UTC is broadcast through short wave radio and satellite.

 Satellites can given an accuracy of about ±0.5ms.

15 Clock Synchronization…………. Algorithms (4)

Cristian’s Algorithm

 Cristian [1989] suggested the use of a time server, connected to a device that receives signals from a source of UTC,

to synchronize computers externally.

 The simplest centralized algorithm for setting time, it issues a RPC to time server and obtain the time.

 A machine sends a request to time server in “d/2” seconds where d= maximum differ between a clock and UTC.

 The time server sends a reply with current UTC (CUTC) when receives the request.

 The machine measures the time delay between time server sending the message and machine receiving it.

 Then it uses the measure to adjust the clock.

 Passive Time Server: when the time server is passive it doesn’t spontaneously send time info to clients until they

request it.
16 Clock Synchronization…………. Algorithms (5)

T0 T1
Client
Reply
Request
CUTC=>Current UTC
Time Server Time

Figure 3. Clock synchronization using a time server

 The best estimation of message propagation time= (T0 + T1)/2. The new time can be set to the time returned by

server plus time that elapsed since the server generated the timestamp:
Tnew =Tserver + (T0 + T1)/2
17 Clock Synchronization…………. Algorithms (6)
Berkeley algorithm

 The Berkeley algorithm, developed by Gusella and Zatti in 1989 for achieving internal synchronization, does not assume

that any machine has an accurate time source with which to synchronize.

 Instead, it chooses for obtaining an average time from the participating computers and synchronizing all machines to that

average. In it, a coordinator computer is chosen to act as the master and the others are slaves.

 The server polls each machine periodically, asking it for the time.

 Based on the answer, it computes an average time and tells all the other machine to advance their clocks to the new time or

slow their clocks down until some specific reduction has been achieved.

 This method is suitable for a system in which no machine has a UTC receiver.

 Active Time Server: a time server that doesn’t wait for clients request rather the time server periodically broadcasts its clock

time.
18 Clock Synchronization…………. Algorithms (7)

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.

Daemon- a program that runs automatically or on a schedule without user interaction

19 Logical Clocks (1)

 What usually matters is that processes agree on the order in each events occur rather than the time at which they occurred.

 Absolute time is not important

 Use logical clocks.

 No concept of happened-when

 Logical time (only relative time, not exact time), is not based on timing but on ordering of events.

 Logical clocks can only advance forward, not in reverse.

 Non-interacting processes cannot share a logical clock.

 If two machine do not interact, there is no need to synchronize them.

 Computers generally obtain logical time using interrupts to update a software clock.
20 Logical Clocks (2)

 The most common logical clock synchronization algorithm for distributed system is Lamport’s Algorithm.

 It is used in situations where ordering is important not time.

Lamport Algorithm

 To synchronize logical clocks, Lamport defined a relation called happens-before notation.

The expression a ~ b is read "a happens before b" and means that all processes agree that first event a occurs, then

afterward, event b occurs.

The happens-before relation can be observed directly in two situations:

1. If a and b are events in the same process, and a occurs before b, then a ~ b is true.

2. If a is the event of a message being sent by one process, and b is the event of the message being received by

another process, then a ~ b.

21 Logical Clocks (3)

 Each message carries a timestamp of the sender clock.

 When a message arrives:

 If receiver’s clock < message timestamp, set system clock to (message timestamp + 1)

 Else do nothing

 Clock must be advanced between any two events in the same process.

Algorithm for sending. Algorithm for receiving.

 time=time + 1;  (message, timestamp)= receive();

 timestamp=time;  time= max(timestamp, time)+1;

 send(message, timestamp);
22 Logical Clocks (4)

Example: Three processes, each with its own clock, the clocks run at different rates.

Msg. 1

T(p2)>T(p1)
Msg. 2

T(p3)>T(p2)

Msg. 3

T(p2)<T(p3)
Msg. 4

T(p1)<T(p2)
23 Logical Clocks (5)

 By applying Lamport algorithm correct the clocks.

According to Lamport algorithm P1 P2 P3

0 0 0
If (Trecv<MsgTS) 6 8 10
{Time=MsgTS+1;} 12 16 20
Else {do nothing} 18 24 30
 So, nothing will be done on Msg1 and Msg2 24 32 40
 On Msg3 T(p2)<T(p3), so P2 should adjust 30 40 50

its clock. Time=Msg3TS+1, 60+1=61 36 48 60

42 61 70
 i.e adds 5 on the previous time so the next
48 69 80
timestamps also adds 5 on the previous time.
54 77 90
60 85 100
24 Logical Clocks (6)

 On Msg4 T(p1)<T(p2), so P1 should adjust its

clock. Time=Msg4TS+1, 69+1=70 P1 P2 P3
 i.e adds 16 on the previous time so the next 0 0 0
timestamps also adds 16 on the previous time. 6 8 10
12 16 20
18 24 30
24 32 40
30 40 50
36 48 60
42 61 70
48 69 80
70 77 90
76 85 100
25 Reading Assignment

 Mutual Exclusion

 Election Algorithm