SUBJECT : DISTRIBUTED

COMPUTING

MODULE 3.0 - SYNCHRONIZATION

1 By – Shrutika Khobragade
3.0 SYNCHRONIZATION
3.1 - Clock Synchronization, Logical Clocks, Election
Algorithms, Mutual Exclusion, Distributed Mutual
Exclusion-Classification of mutual Exclusion
Algorithm, Requirements of Mutual Exclusion
Algorithms, Performance measure.

3.2 Non Token based Algorithms: Lamport Algorithm,

Ricart–Agrawala‘s Algorithm, Maekawa‘s Algorithm

3.3 Token Based Algorithms: Suzuki-Kasami‘s

Broardcast Algorithms, Singhal‘s Heurastic Algorithm,
Raymond‘s Tree based Algorithm, Comparative
Performance Analysis. 2
CLOCK SYNCHRONIZATION
? In the Distributed Systems (DS) 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.

? Clock synchronization is a method of synchronizing

clock values of any two nodes in a distributed system with
the use of external reference clock or internal clock value of
the node. 3
CLOCK SYNCHRONIZATION
? Each node in a distributed system can share
their resources, e.g. the producer consumer
processes and the client-server processes, sharing
of printer or scanner
? Resources like a printer and scanner cannot be
used by multiple processes simultaneously, so it
must wait for one process to complete and then
give chance to the next process.
? So there is a need of proper allocation of available
resources, to preserve the state of resources and
coordination between processes. To resolve these
conflicts, clock synchronization is important. 4
CLOCK SYNCHRONIZATION
? Clock synchronization can be implemented by using
the physical local clock of each node.
? Some of the following example shows the problems
with unsynchronized clocks:
? a) In a distributed banking system, if the timing and
ordering of financial transactions are not tracked, it
may raise inconsistent state in the system.
? b) A distributed online reservation system in which the
last available seat may get booked from multiple nodes
if their local clocks are not synchronized.
? c) There is a need to transmit a message from one node
to another at any time. This will become difficult if
sender and receiver clocks are not synchronized with
each other. 5
CLOCK SYNCHRONIZATION
? The physical clocks are used to adjust the time of nodes.
Each node in the system can share its local time with
other nodes in the system. The time is set based on UTC
(Universal Time Coordination). UTC is used as a
reference time clock for the nodes in the system.
? The clock synchronization can be achieved by 2 ways:
External and Internal Clock Synchronization.
? External clock synchronization is the one in which
an external reference clock is present. It is used as a
reference and the nodes in the system can set and adjust
their time accordingly.
? Internal clock synchronization is the one in which
each node shares its time with other nodes and all the
nodes set and adjust their times accordingly. 6
 CLOCK SYNCHRONIZATION
There are 2 types of clock synchronization algorithms: Centralized
and Distributed.

? Centralized is the one in which a time server is used as a

reference. The single time server propagates its time to the
nodes and all the nodes adjust the time accordingly. It is
dependent on single time server so if that node fails, the whole
system will lose synchronization. Examples of centralized are-
Berkeley Algorithm, Passive Time Server, Active Time Server
etc.
? Distributed is the one in which there is no centralized time
server present. Instead the nodes adjust their time by using
their local time and then, taking the average of the differences
of time with other nodes. Distributed algorithms overcome the
issue of centralized algorithms like the scalability and single
point failure. Examples of Distributed algorithms are – Global
Averaging Algorithm, Localized Averaging Algorithm, NTP 7
(Network time protocol) etc.
 LOGICAL CLOCK
8
LOGICAL CLOCK
? Logical Clocks refer to implementing a protocol on
all machines within your distributed system, so that
the machines are able to maintain consistent
ordering of events within some virtual time span.
? A logical clock is a mechanism for capturing
chronological and causal relationships in a
distributed system.
? Distributed systems may have no physically
synchronous global clock, so a logical clock allows
global ordering on events from different processes in
such systems.
9
 LOGICAL CLOCK

? Example :
If we go outside then we have made a full plan that at
which place we have to go first, second and so on. We
don’t go to second place at first and then the first place.
We always maintain the procedure or an organization
that is planned before. In a similar way, we should do
the operations on our PCs one by one in an organized
way.
? Suppose, we have more than 10 PCs in a distributed
system and every PC is doing it’s own work but then
how we make them work together. There comes a
solution to this i.e. LOGICAL CLOCK. 10
 LOGICAL CLOCK
? If we give each PC their individual number than it will be
organized in a way that 1st PC will complete its process
first and then second and so on. BUT, Timestamps will
only work as long as they obey causality.

? What is causality ?
Causality is fully based on HAPPEN BEFORE
RELATIONSHIP.
? Taking single PC only if 2 events A and B are occurring
one by one then TS(A) < TS(B). If A has timestamp of 1,
then B should have timestamp more than 1, then only
happen before relationship occurs.
? Taking 2 PCs and event A in P1 (PC.1) and event B in P2
(PC.2) then also the condition will be TS(A) < TS(B).
Taking example- suppose you are sending message to
someone at 2:00:00 pm, and the other person is receiving it
at 2:00:02 pm. Then it’s obvious that TS(sender) < 11
TS(receiver).
LOGICAL CLOCK

? Properties Derived from Happen Before

Relationship –
? Transitive Relation –
If, TS(A) <TS(B) and TS(B) <TS(C), then TS(A) <
TS(C)
? Causally Ordered Relation –
a->b, this means that a is occurring before b and
if there is any changes in a it will surely reflect
on b.
? Concurrent Event –
This means that not every process occurs one by
one, some processes are made to happen
simultaneously i.e., A || B. 12
LOGICAL CLOCK - LAMPORT
• Lamport’s clocks are a simple technique used for
determining the order of events in a distributed
system.

• This clock was proposed by Leslie Lamport , a Lamport

clock maintains order of operations by incrementing a
counter contained in the events

• By simply adding a counter value to events as they are

received and incrementing this value based on the last
seen value,
13

• Lamport clocks provide a partial ordering of events –

LAMPORT LOGICAL CLOCK RULES
• A process increments its counter before each event in that process;
• When a process sends a message, it includes its counter value with
the message;
• On receiving a message, the counter of the recipient is updated, if
necessary, to the greater of its current counter and the timestamp in
the received message. The counter is then incremented by 1 before
the message is considered received.
? The algorithm for sending:
• time = time+1;
• time_stamp = time;
• send(message, time_stamp);
? The algorithm for receiving:
• (message, time_stamp) = receive();
• time = max(time_stamp, time)+1; 15
 ELECTION ALGORITHM (REFER
PDF)

17
 MUTUAL
EXCLUSION,
DISTRIBUTED MUTUAL EXCLUSION-
CLASSIFICATION OF MUTUAL
EXCLUSION ALGORITHM
18
MUTUAL EXCLUSION
? Mutual exclusion is a concurrency control
property which is introduced to prevent race
conditions.
? It is the requirement that a process can not enter
its critical section while another concurrent
process is currently present or executing in its
critical section i.e only one process is allowed to
execute the critical section at any given instance
of time.

19
 MUTUAL EXCLUSION
? Mutual exclusion in single computer system Vs.
distributed system:
In single computer system, memory and other resources are
shared between different processes. The status of shared
resources and the status of users is easily available in the
shared memory so with the help of shared variable (For
example: Semaphores) mutual exclusion problem can be
easily solved.

? In Distributed systems, we neither have shared memory nor

a common physical clock and there for we can not solve
mutual exclusion problem using shared variables. To
eliminate the mutual exclusion problem in distributed
system approach based on message passing is used.
? A site in distributed system do not have complete
information of state of the system due to lack of shared
memory and a common physical clock. 20
REQUIREMENTS OF MUTUAL EXCLUSION
ALGORITHM:
? No Deadlock:
Two or more site should not endlessly wait for any message
that will never arrive.
? No Starvation:
Every site who wants to execute critical section should get
an opportunity to execute it in finite time. Any site should
not wait indefinitely to execute critical section while other
site are repeatedly executing critical section
? Fairness:
Each site should get a fair chance to execute critical section.
Any request to execute critical section must be executed in
the order they are made i.e Critical section execution
requests should be executed in the order of their arrival in
the system.
? Fault Tolerance:
In case of failure, it should be able to recognize it by itself in 21
order to continue functioning without any disruption.
MUTUAL EXCLUSION

? Below are the 2 approaches based on message passing

to implement mutual exclusion in distributed systems:
? Token Based Algorithm:
⚫A unique token is shared among all the sites.
⚫ If a site possesses the unique token, it is allowed to enter
its critical section
⚫ This approach uses sequence number to order requests for
the critical section.
⚫ Each requests for critical section contains a sequence
number. This sequence number is used to distinguish old
and current requests.
⚫ This approach insures Mutual exclusion as the token is
unique
⚫ Example: Suzuki-Kasami’s Broadcast Algorithm 22
MUTUAL EXCLUSION
? Non-token based approach: A site communicates with
other sites in order to determine which sites should execute
critical section next. This requires exchange of two or more
successive round of messages among sites.
? This approach use timestamps instead of sequence number
to order requests for the critical section.
? When ever a site make request for critical section, it gets a
timestamp. Timestamp is also used to resolve any conflict
between critical section requests.
? All algorithm which follows non-token based approach
maintains a logical clock. Logical clocks get updated
according to Lamport’s scheme
? Example: Lamport's algorithm, Ricart–Agrawala
algorithm 23
CENTRALISED ALGORITHM
? The most straightforward way to achieve mutual.
exclusion in a distributed system is to simulate
how it is done in a one-processor system.
? One process is elected as the coordinator.
Whenever a process wants to access a shared
resource, it sends a request message to the
coordinator stating which resource it wants to
access and asking for permission.
? If no other process is currently accessing that
resource, the coordinator sends back a reply
granting permission, as shown in the image.
When the reply arrives, the requesting process
can go ahead. 24
CENTRALISED ALGORITHM

25
 3.2 NON TOKEN BASED ALGORITHMS:

LAMPORT ALGORITHM,
RICART–AGRAWALA‘S ALGORITHM,
MAEKAWA‘S ALGORITHM

(FOR DIAGRAM AND EXAMPLE

USE PDF)
26
 LAMPORT ALGORITHM
27
LAMPORT AGORITHM – NON TOKEN
? Lamport designed a distributed MUTEX
algorithm on the basis of the concept of logical
clock .
? Uses a non-token based scheme.
? Non-token based protocols use timestamps to
order requests for CS. Request message Contain
following
1. Identifier (Machine id /process id)
2. Timestamp
3. Name of resource
28
LAMPORT AGORITHM – NON TOKEN
? Timestamp is a distinctive integer value which is
given by the operating system to the process when
they produce requests for CS.
? Timestamp is rapidly increased every time when a
request is reached.
? Lesser timestamp requests have higher precedence
rather than big timestamps requests.
? In lamport’s algorithm, for a process Pi, request set
Ri= {P1, P2, P3…….Pn}. It contains of all those
process from which Pi must require permission before
entering the CS.
? Every process maintains a queue of awaiting requests
29
for entering CS in the ascending order of timestamps.
 LAMPORT AGORITHM – NON TOKEN
Requesting the critical section:
? When a process wants to enter into CS, it follows
the following steps:

1. Enters its request in its own queue (ordered by

time stamps).
2. Sends a request to all other nodes.
3. Wait for replies from all other nodes.
4. When another process receives this request
message, it sends a timestamp reply message to
the requesting process and keeps this request in
its own request queue. 30
LAMPORT AGORITHM – NON TOKEN
Executing the critical section:
A process can enter into CS when these two
conditions are satisfied:

1. Pi has not received a message with timestamp

larger than its from all other process.

1. Pi’s request is at the top of request_ queue.

31
 LAMPORT AGORITHM – NON TOKEN
Releasing the critical section:
1. For exiting the critical section, it removes its
request from the queue and sends a release
message to every process.

1. Upon receiving release message form the process,

then other process removes the related entry from
its own request queue.

1. If own request is at the top of its queue and all

replies have been received, enter into critical 32
section.
 RICART–AGRAWALA‘S ALGORITHM-
NON TOKEN
33
RICART–AGRAWALA‘S ALGORITHM- NON
TOKEN

? Ricart-agrawala algorithm is an expansion and

optimization of Lamport’s protocol.
? This algorithm combines the RELEASE and
REPLY message of lamport’s algorithm and
decreases the complexity of the algorithm by (N-
1)
? In this algorithm, there is a request set Pi= (P1,
P2, P3……Pn). It comprises of all the sites from
which a site needs to acquire authorization before
entering to CS.

34
RICART–AGRAWALA‘S ALGORITHM- NON
TOKEN

Requesting the critical section

1. When a site desires to execute into CS, it sends
a request along with its timestamp to all sites.
This message includes the site's name, and the
current timestamp of the system according to its
logical clock.
2. 2. Upon reception of a request message, another
site will immediately sends a time stamped
reply message if and only if:

35
RICART–AGRAWALA‘S ALGORITHM- NON
TOKEN

Requesting the critical section

1. The receiving process is not currently interested
in the critical section.
2. The receiving process desires to enter into CS
but its own timestamp value is higher than
requesting site.
3. The requesting process will deferred the reply
message. This means that a reply will be sent
only after the receiving process has completed
using the CS itself.
36
RICART–AGRAWALA‘S ALGORITHM- NON
TOKEN

Executing the critical section

? Requesting site enter its Cs only after receiving
all reply messages

Releasing the critical section

1. Upon exiting the critical section, the site sends
all deferred reply messages.
2. In this algorithm, all the CS requests are
executed in their timestamp order.

37
 MAEKAWA’S ALGORITHM
38
 MAEKAWA’S ALGORITHM
Algorithm:
To enter Critical section:
1. When a site Si wants to enter the critical section, it sends a
request message REQUEST(i) to all other sites in the
request set Ri.
2. When a site Sj receives the request
message REQUEST(i) from site Si, it returns
a REPLY message to site Si if it has not sent
a REPLY message to the site from the time it received the
last RELEASE message. Otherwise, it queues up the
request.

39
MAEKAWA’S ALGORITHM
To execute the critical section:
? A site Si can enter the critical section if it has received
the REPLY message from all the site in request
set Ri

To release the critical section:

1. When a site Si exits the critical section, it
sends RELEASE(i) message to all other sites in
request set Ri
2. When a site Sj receives the RELEASE(i) message
from site Si, it send REPLY message to the next site
waiting in the queue and deletes that entry from the
queue
3. In case queue is empty, site Sj update its status to
show that it has not sent any REPLY message since 40
the receipt of the last RELEASE message
 TOKEN BASED ALGORITHMS:

SUZUKI-KASAMI‘S BROADCAST
ALGORITHMS,
SINGHAL‘S HEURASTIC ALGORITHM,
RAYMOND‘S TREE BASED
ALGORITHM,
COMPARATIVE PERFORMANCE
ANALYSIS.
41
 SUZUKI KASAMI ALGORITHM
42
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED
? For theory refer PDF and research paper
shared.

43
SUZUKI-KASAMI‘S BROADCAST
ALGORITHM- TOKEN BASED

44
SUZUKI-KASAMI‘S BROADCAST
ALGORITHM- TOKEN BASED

45
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

46
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

47
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

48
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

49
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

50
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

51
SUZUKI-KASAMI‘S BROADCAST ALGORITHM-
TOKEN BASED

Drawbacks of Suzuki–Kasami Algorithm

? Non-symmetric Algorithm: A site retains the token

even if it does not have requested for critical section.
? According to definition of symmetric Algorithm “No
site possesses the right to access its critical section
when it has not been requested.”
? Messages Overhead
? Synchronization delay is 0 and no message is needed
if the site holds the idle token at the time of its
request.
? Transmission time and a maximum of N message is
required per critical section invocation. 52
 RAYMOND TREE ALGORITHM
(FOR EXAMPLE REFER PDF)
53
RAYMOND TREE ALGORITHM – TOKEN BASED

? Raymond’s tree based algorithm is lock

based algorithm for mutual exclusion in a
distributed system in which a site is allowed to
enter the critical section if it has the token.
? In this algorithm, all sites are arranged as a
directed tree such that the edges of the tree are
assigned direction towards the site that holds
the token.
? Site which holds the token is also called root of
the tree.
54
RAYMOND TREE ALGORITHM – TOKEN BASED
Algorithm:
? To enter Critical section:

❑ When a site Si wants to enter the critical section it

sends a REQUEST message to the node along the
directed path to the root, provided it does not hold the
token and its request_q is empty. After
sending REQUEST message it add its request to
its request_q.
❑ When a site Sj on the path to the root receives
the REQUEST message of site Si, it places
the REQUEST in its request_q and sends
the REQUEST message along the directed path to the
root, if it has not sent any REQUEST message for
previously received REQUEST message. 55
RAYMOND TREE ALGORITHM – TOKEN BASED

❑ When the root site Sr( having token) receives

the REQUEST message, it sends the token to
the requesting site and sets its holder variable
to point at that site.
❑ On receiving the token, Site Sj deletes the top

entry from its request_q and sends the token

to the site indicated by deleted
entry. holder variable of Site Sj is set to point
at that site.
To execute the critical section: Site Si executes
the critical section if it has received the token and
56
its own entry is at the top of its request_q.
RAYMOND TREE ALGORITHM – TOKEN BASED

To release the critical section:

❑

After finishing the execution of the critical section, site

Si does the following: If its request_q is non-empty,
then it deletes the top msot entry from
its <request_q and then it sends the token to that site
indicated by deleted entry and also its holder variable
is set to point at that site.
❑ After performing above action, if the request_q is still
non-empty, then site Si sends a REQUEST message
to the site pointed by holder variable in order to get
57
token back
 SINGHAL’S HEURISTIC
ALGORITHM
58
please refer pdf for example
59
 PERFORMANCE ANALYSIS
60
61