Distributed Computing

Prof. Smita S. Mane

Asst. Prof.
Dept. of AI & DS,
VESIT, Chembur
 Module – 3
Synchronization
3.1 Clock Synchronization, Physical Clock, 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 Broadcast Algorithms, Singhal‘s Heuristic Algorithm,
Raymond‘s Tree.based Algorithm, Comparative Performance Analysis.
Introduction
● Distributed System is a collection of computers connected via a
high-speed communication network.
● In the distributed system, the hardware and software
components communicate and coordinate their actions by
message passing.
● Each node in distributed systems can share its resources with
other nodes.
● So, there is a need for proper allocation of resources to preserve
the state of resources and help coordinate between the several
processes.
● To resolve such conflicts, synchronization is used.
 Introduction
● Synchronization in distributed systems is achieved via clocks.
● 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.
● Clock synchronization can be achieved by 2 ways:
1) External Clock Synchronization.
2) Internal Clock Synchronization.
Introduction
● 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.
● Synchronization in centralized systems is primarily
accomplished through shared memory.
● Event ordering is clear because all events are timed by the same
clock Synchronization in distributed systems is harder
–No shared memory
–No common clock
Global Time
■ Global Time is utilized to provide timestamps
for processes and data.
✔ Physical clock: concerned with “People” time
✔ Logical clock: concerned with relative time
and maintain logical consistency
Obtaining an Accurate Physical
Time
■ A physical time server is needed to access the current
time from a universal time coordinator (UTC).
■ Two sources for UTC:

1) WWV shortwave radio station in Ft. Collins,

Colorado
2) Geostationary Operational Environmental Satellites
(GEOS)
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.
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).
For example

E F
Process 3

C D
Process 2

A B
Process 1

A>B>C>D>F E
 Election algorithm
● Distributed Algorithm is an algorithm that runs on a distributed
system.
● Distributed system is a collection of independent computers that do
not share their memory. Each processor has its own memory and they
communicate via communication networks. Communication in
networks is implemented in a process on one machine communicating
with a process on another machine.
● Many algorithms used in the distributed system require a coordinator
that performs functions needed by other processes in the system.
● Election algorithms are designed to choose a coordinator.
Election Algorithms:
● Election algorithms choose a process from a group of processors to
act as a coordinator.
● If the coordinator process crashes due to some reasons, then a new
coordinator is elected on other processor.
● Election algorithm basically determines where a new copy of the
coordinator should be restarted.
● Election algorithm assumes that every active process in the system
has a unique priority number.
● The process with highest priority will be chosen as a new coordinator.
Hence, when a coordinator fails, this algorithm elects that active
process which has highest priority number.
● Then this number is send to every active process in the distributed
system. We have two election algorithms for two different
configurations of a distributed system.
1) Bully Algorithms:
● This algorithm applies to system where every process can send a
message to every other process in the system.
1) Bully Algorithms:
● Algorithm – Suppose process P sends a message to the coordinator.
1) If the coordinator does not respond to it within a time interval T, then
it is assumed that coordinator has failed.
2) Now process P sends an election messages to every process with high
priority number.
3) It waits for responses, if no one responds for time interval T then
process P elects itself as a coordinator.
4) Then it sends a message to all lower priority number processes that it
is elected as their new coordinator.
5) However, if an answer is received within time T from any other
process Q,
(I) Process P again waits for time interval T’ to receive another message
from Q that it has been elected as coordinator.
(II) If Q doesn’t responds within time interval T’ then it is assumed to
have failed and algorithm is restarted.
2) Ring Algorithms:
● This algorithm applies to systems organized as a ring(logically or
physically).
● In this algorithm we assume that the link between the process are
unidirectional and every process can message to the process on its
right only.
● Data structure that this algorithm uses is active list, a list that has a
priority number of all active processes in the system.
2) Ring Algorithms:
1) If process P1 detects a coordinator failure, it creates new active list
which is empty initially. It sends election message to its neighbour on
right and adds number 1 to its active list.
2) If process P2 receives message elect from processes on left, it
responds in 3 ways:
(I) If message received does not contain 1 in active list then P1 adds 2 to
its active list and forwards the message.
(II) If this is the first election message it has received or sent, P1 creates
new active list with numbers 1 and 2. It then sends election message 1
followed by 2.
(III) If Process P1 receives its own election message 1 then active list for
P1 now contains numbers of all the active processes in the system. Now
Process P1 detects highest priority number from list and elects it as the
new coordinator.
3.1 Clock Synchronization, Physical Clock, 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 Broadcast Algorithms, Singhal‘s Heuristic Algorithm,
Raymond‘s Tree.based Algorithm, Comparative Performance Analysis.
● Race conditions are occur when two computer
program processes, or threads, attempt to access the
same resource at the same time and cause problems in
the system.
 Mutual Exclusion
● Mutual exclusion ensures that concurrent processes make a
serialized access to shared resources or data.
The well known critical section problem!
● In a distributed system neither shared variables
(semaphores) nor a local kernel can be used in order to
implement mutual exclusion! Thus, mutual exclusion has to be
based exclusively on message passing, in the context of
unpredictable message delays and no complete knowledge of
the state of the system.
● Sometimes the resource is managed by a server which
implements its own lock together with the
● synchronization are transparent for the process accessing the
resource. This is typically the case for database systems with
transaction processing.
● Race conditions are prevent by Mutual Exclusion.
 Mutual Exclusion
● A mechanism has to be implemented at the level of the process
requesting for access.
● Basic requirements for a mutual exclusion mechanism:
1) safety: at most one process may execute in the critical section
(CS) at a time;
2) liveness: a process requesting entry to the CS is eventually
granted it (so long as any process executing the CS eventually
leaves it). Liveness implies freedom of deadlock and starvation.
● Approaches for distributed mutual exclusion:
1) Token based approach
2) Non-token based approach
3) Quorum based approach
Mutual Exclusion Requirements
1) Safety Property: At any instant, only one process can execute
the critical section.
2) Liveness Property: This property states the absence of
deadlock and starvation. Two or more sites should not endlessly
wait for messages which will never arrive.
3) Fairness: Each process gets a fair chance to execute the CS.
Fairness property generally means the CS execution requests
are executed in the order of their arrival (time is determined by
a logical clock) in the system.
Performance Metrics
The performance is generally measured by the following four metrics:
1) Message complexity: The number of messages required per CS
execution by a site.
2) Synchronization delay: After a site leaves the CS, it is the time
required and before the next site enters the CS (see Figure 1).

Last site exits the CS Next site enters the CS

time
Synchronization delay

Figure 1: Synchronization Delay.

Performance Metrics
Response time: The time interval a request waits for its CS execution to
be over after its request messages have been sent out (see Figure 2)

The site enters

CS Request arrives Its request the CS The site exits the CS
messages sent out

CS execution time time

Response Time

Figure 2: Response Time.

System throughput: The rate at which the system executes requests for
the CS.
system throughput=1/(SD+E )
where SD is the synchronization delay and E is the average critical
section execution time.
Distributed Mutual Exclusion Algorithms 37 / 93
3.1 Clock Synchronization, Physical Clock, 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 Broadcast Algorithms, Singhal‘s Heuristic Algorithm,
Raymond‘s Tree.based Algorithm, Comparative Performance Analysis.
Non Token based Algorithms
● In Non-Token based algorithm, there is no token even not any
concept of sharing token for access.
● Uses the timestamp to order the request for the Computer
Systems and to resolve the conflict for the simultaneous requests
for the System.
● Two or more successive rounds of messages are exchanged
among the sites to determine which site will enter the CS next.
➔ Lamport Algorithm
➔ Ricart–Agrawala‘s Algorithm
➔ Maekawa‘s Algorithm
 1) Lamport Algorithms
● Requests for CS are executed in the increasing order of
timestamps and time is determined by logical clocks.
● Every site Si keeps a queue request queue i , which contains
mutual exclusion requests ordered by their timestamps.

Reff Video
Advantages
1) Simplicity: Lamport’s algorithm is relatively easy to
understand and implement compared to other
algorithms for mutual exclusion in distributed systems.
2) Fairness: The algorithm guarantees fairness by
providing a total order of events that is used to
determine the next process that can enter the critical
section.
3) Scalability: Lamport’s algorithm is scalable because it
only requires each process to communicate with its
neighbors, rather than all other processes in the
system.
4) Compatibility: The algorithm is compatible with a wide
range of distributed systems and can be adapted to
different network topologies and communication
protocols.
Disadvantages
1) Message Overhead: The algorithm requires a lot of
message passing between processes to maintain the
total order of events, which can lead to increased
network traffic and latency.
2) Delayed Execution: The algorithm can lead to delays in
the execution of critical sections because a process may
have to wait for messages to arrive from other processes
before entering the critical section.
3) Limited Performance: The algorithm may not perform
well in systems with a high number of processes
because of the increased message overhead and
delayed execution.
4) No Fault Tolerance: The algorithm does not provide any
fault tolerance mechanism, which means that if a
process fails or crashes, it may cause the entire system
to fail or become unstable.
Reff Video
Reff Video
3.1 Clock Synchronization, Physical Clock, 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 Broadcast Algorithms, Singhal‘s Heuristic Algorithm,
Raymond‘s Tree.based Algorithm, Comparative Performance Analysis.
 Suzuki-Kasami‘s Broadcast

● Token-based algorithm
● Modification of Ricart–Agrawala algorithm
● In token-based algorithms, A site is allowed to enter its critical
section if it possesses the unique token.
● Non-token based algorithms uses timestamp to order requests for
the critical section whereas sequence number is used in token
based algorithms.
● Each requests for critical section contains a sequence number. This
sequence number is used to distinguish old and current requests.
Data structure and Notations

● An array of integers RN[1…N]

● A site Si keeps RNi[1…N], where RNi[j] is the largest sequence
number received so far through REQUEST message from site
Si.
● An array of integer LN[1…N]
● This array is used by the token.LN[J] is the sequence number of
the request that is recently executed by site Sj.
● A queue Q
● This data structure is used by the token to keep record of ID of
sites waiting for the token
To enter Critical section:
● When a site Si wants to enter the critical section and it does not
have the token then it increments its sequence number RNi[i]
and sends a request message REQUEST(i, sn) to all other sites
in order to request the token.
● Here sn is update value of RNi[i]
● When a site Sj receives the request message REQUEST(i, sn)
from site Si, it sets RNj[i] to maximum of RNj[i] and sn i.e
RNj[i] = max(RNj[i], sn).
● After updating RNj[i], Site Sj sends the token to site Si if it has
token and RNj[i] = LN[i] + 1
To execute the critical section:
● Site Si executes the critical section if it has acquired the
token.
To release the critical section:
● After finishing the execution Site Si exits the critical section and does
following:
● sets LN[i] = RNi[i] to indicate that its critical section request RNi[i]
has been executed
● For every site Sj, whose ID is not present in the token queue Q, it
appends its ID to Q if RNi[j] = LN[j] + 1 to indicate that site Sj has
an outstanding request.
● After above updation, if the Queue Q is non-empty, it pops a site ID
from the Q and sends the token to site indicated by popped ID.
● If the queue Q is empty, it keeps the token
3.1 Clock Synchronization, Physical Clock, 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 Broadcast Algorithms, Singhal‘s Heuristic Algorithm,
Raymond‘s Tree.based Algorithm, Comparative Performance Analysis.
3.1 Clock Synchronization, Physical Clock, 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 Broadcast Algorithms, Singhal‘s Heuristic Algorithm,
Raymond‘s Tree.based Algorithm, Comparative Performance Analysis.
●Thanks
for your attention