Chapter-3

Kanchan K Doke
Computer Engg. Department , BVCOE
 2

Outline
• Clock synchronization
▫ Physical clock
▫ Logical clock
• Election algorithm
▫ Ring algorithm
▫ Bully algorithm
• Mutual exclusion
▫ Centralized
▫ Distributed
• Deadlock
▫ Centralized
▫ Distributed
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 3

Introduction
 A DS consists of a collection of distinct processes that are
separated spatially and run concurrently
 Sharing of resources may be co-operative or competitive.
 The rules for enforcing correct interaction are implemented in the
form of synchronization.
 The number of resources in a computing system is restricted , one
process must influence the action of other concurrently executing
processes as it competes for resources.
 The synchronization mechanisms suitable for distributed system
are
1. Clock synchronization
2. Event ordering
3. Mutual exclusion
4. Election algorithm

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 4

1. Physical clock
2. Logical clock

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 5

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

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 6

Clock synchronization
• Why synchronization:-
▫ An application may have processes that concurrently
run on multiple nodes of the system
▫ It enables to measure the duration of distributed
activities that start on one node and terminate on
another
• Issues :-
 Practically no two clocks can be perfectly synchronized
 Clock synchronization requires each node to read other nodes’ clock
 Time must never run backward

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 7

Marks 10

Physical Clocks
• There are two aspects:
Obtaining an accurate value for physical time

Synchronizing the concept of physical time

throughout the distributed system

These can be implemented using centralized

algorithms or distributed algorithms

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 8

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:

 WWV shortwave radio station in Ft. Collins,
Colorado
 Geostationary Operational Environmental Satellites
(GEOS)

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 10

Marks 10

Christian's Algorithm… Passive Timer Server

• Periodically with period T, each machine asks the time

server for the current time by making RPC
• The server responds with the current time, CUTC (Universal
Coordinated Time)
• The client set its clock to CUTC

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 11

Marks: 5/10

Christian's Algorithm… Passive Timer Server

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 12

Marks: 5/10

Berkeley Algorithm……Active Time server

• The time server (daemon) is active:
▫ Time server polls every machine periodically to
ask what time is there
▫ Based on the answers, it computes an average
time
▫ Tells all other machines to advance their clocks to
the new time or slow their clocks down until some
specified reduction has been achieved.
▫ Propagation is taken into account.
• The time server’s time is set manually by
operator periodically.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 13

Berkeley Algorithm
The Berkeley0+(-10)+25=15/3=5
Algorithm
Time server

10+5=
25-5=

a) The time server asks all the other machines for their clock values using
a polling mechanism and providing “current time”
b) The machines answer indicating how they differ from time sent.
c) The time server tells everyone how to adjust their clock based on a
calculation of the “average time value”.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 14

Event Ordering
 For most applications it is not necessary to keep the clocks
synchronized.

 It is sufficient to ensure that, all events that occur in a DS be

totally ordered in a consistent manner with an observed behavior.

 For partial ordering of events Happened-Before and logical clocks

relation is used.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 15

Marks 10

Event Ordering…….(cont.)
Happened-Before relation
 The happened-before relation ()on a set of events
satisfies
1. If a and b are events in the same process and a
occurs before b, then ab.
2. If a is the event of sending message to b, and b is the
event of receiving from a then ab
3. If ab and bc, the ac (transitive law)
4. if a and b are said to be concurrent, then ab is not
possible.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 16

Event ordering --Happened-Before relation

•  relations:
p1  q2
r0  q4
q3  r4
q1  p4
• Concurrent events:
q0 and p2
r0 and q3
r0 and p3
q3 and p3

Space- time diagram

• Wavy line means sending/receiving
a message
• Events are concurrent if no line
exists between them
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 18

Logical clocks concept

 It is a way to associate a timestamp (a number
independent of any clock time) with each system event
for ordering the events.
 Each process Pi has a clock Ci associated with a number
Ci(a) to any event a
 The counters acts as logical clocks
 At beginning, counters are initialized to zero
 A process increments its counter by 1 whenever an event occurs
 For receiving message, the counter value should always greater
than the counter value of sender.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 20

Marks 5

Logical Ordering

Conditions
C1: If a and b are two events within the same process Pi
and a occurs before b, then Ci(a)<Ci(b)

C2: If a is sending a message by Pi and b is the receipt of

that message by process Pj , then Ci (a)<Cj (b)

C3: A clock of Ci associated with process Pi must always

go forward

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 21

For example
E F
Process 3

Process 2 C D

Process A B
1

A<B<C<D<F> E

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 22

Marks 10

Lamport’s Algorithm
• To implement Lamport’s logical clocks, each
process Pi maintains a local counter Ci that is
updated as follows:
Step 1. Before executing an event, Pi executes
Ci ← Ci +1
Step 2. When process Pi sends a message m to Pj , it sets m’s
timestamp ts(m) = Ci after having executed the previous step.
Step 3. Upon the receipt of a message m, process Pj adjusts its own
local counter as
 Cj ← max{Cj ,ts(m)} +1
 after which it then executes the first step and delivers the
message to the application.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 23

Lamport’s Algorithm:- for example

F(2)
E(1) F(5)
Process 3
C(1)
C(3) D(4)
Process 2

A(1) B(2)
Process 1

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 24

Lamport’s Logical Clock Algorithm

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

Total Ordering with Logical Clocks Marks 10

25
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 Totally-Ordered Multicasting
Updating a replicated database and leaving it in an inconsistent state.

• Process P1 add 20,000Rs to an account( initial value is 5,000Rs)

• Process P2 increment account by 1%
• There are two replicas
2
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE 6
 27

Total Ordering with Logical Clocks

 An additional requirement, no two events have numerically
identical Lamport timestamps attach the number (identifier) of the
process in which the event occurs at the timestamp.

E(1.3) F(5.3)
Process 3

C(3.2) D(4.2)
Process 2

A(1.1) B(2.1)
Process 1

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

Totally-Ordered Multicasting

28

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 29

Vector Logical Clocks Marks 10

Vector Logical time is better:

 Vector value is timestamp of the event.
 All processes use a vector of counters (logical
clocks)
 ith element is the clock value for process i.
 initially all zero.
 Each process i increments the ith element of its
vector upon an instruction, send or receive
event.
 A send(message) event carries its vector
timestamp (counter vector)
 For a receive(message) event,
Max(Vreceiver[k] , Vmessage[k]), if k≠j
Vreceiver[j] =
Vreceiver[j] + 1 otherwise
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 31

Example: Vector Logical Time

Physical Time

1,0,0,0 2,0,0,0 4,0,2,2

p 1 0,0,0,0 3,0,2,2
(1,0,0,0)
1,2,0,0 (4,0,2,2)
p 2 0,0,0,0
1,1,0,0 (2,0,0,0) (1,2,0,0)
(2,0,2,2)
2,0,2,0
p 3 0,0,0,0
2,0,1,0 2,2,3,0 4,2,4,2 4,2,5,3
(2,0,2,0) (2,0,2,3)
p 4 0,0,0,0
2,0,2,1
2,0,2,2
2,0,2,3

p1,p2,p3,p4  Vector logical clock

(vector timestamp)
Message

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

Vector Clock Algorithm
32

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 33

Marks 10

•The Bully Algorithm

• A Ring Algorithm

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 34

Election Algorithms
• Many distributed systems need one process to act as a
coordinator to initiate actions or to resolve conflicts.
• Assumptions:
▫ We will assume that each process has a unique process number id
so we can attempt to locate the highest numbered process to act
as the coordinator.
▫ Every process knows the id numbers of all other processes.
▫ A process doesn’t not know which of the other processes is up or
down.
• Goal: When an election starts, it ends with all processes
agreeing on who the coordinator is.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 35

Bully Algorithm
• Messages used: Election, Coordinator, OK

• 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.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 36

Bully Algorithm:- For example

1 1 1
7 7 7 2
2 2
Election

6 6 6 3
Election
3 3
5 4 5 4 5 4
Ok

a b c

• Figure :The bully election algorithm.

(a) Process 4 holds an election.
(b) Processes 5 and 6 respond, telling 4 to stop.
(c) Now 5 and 6 each hold an election.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 37

Bully Algorithm:- For example

1 1
7 2 7 2
Coordinator
6 Ok
3 6 3
5 4 5 4
d e
• Figure : The bully election algorithm.
(d) Process 6 tells 5 to stop.
(e) Process 6 wins and tells everyone.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 38

Ring Algorithm
• The ring algorithm uses the same ring arrangement as in the token
ring mutual exclusion algorithm, but does not employ a token this
time.

• Processes are physically or logically ordered so that each knows its

successor.

• If any process detects failure, it constructs an election message with

its process ID (e.g., its network address and local process ID) and
sends it to its neighbor.

• If the neighbor is down, the process skips over it and sends the
message to the next process in the ring. This process is repeated
until a running process is located.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 39

Ring Algorithm
• At each step, the process adds its own process ID to the list in the message
and sends the message to its living neighbor.

• Eventually, the election message comes back to the process that started it.

• The process realizes this because it gets an election message with its own
process ID at the head of the list.
▫ The list of processes in the message represents the list of all live processes in the
system.

• The process then picks either the highest or lowest process ID in the list
and sends out a message to the group informing them of the new
coordinator.

• The method for picking the leader has to be consistent so that even if
multiple election messages circulated, each process that started an election
will come to the same decision on who the coordinator is.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 40

Ring Algorithm

[2,3,4,5,6,0,1]

Initiator

[5,6,0,1,2,3,4] Initiator

Figure : Election algorithm using a ring.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 41

Ring Algorithm

[2,3,4,5,6,0,1]
[Coordinator,6]

[Coordinator,6]
[5,6,0,1,2,3,4]
Figure : Election algorithm using a ring.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 42

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 43

Distributed Mutual Exclusion:

Introduction
• Concurrent access to a shared resource by several
uncoordinated user-requests is serialized to secure the
integrity of the shared resource
• The actions performed by a user on a shared resource
must be atomic.
• For correctness, it is necessary that the shared resource be
accessed by a single site (or process) at a time (eg.
Directory management)

“Mutual exclusion is a property of process

synchronization which states that no two processes
can exist in the critical section at any given point of
time .”
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 44

Single-Computer vs. Distributed System

• Single-computer systems:-
▫ The status of a shared resource and the status of users is
readily available in the shared memory
▫ The mutual exclusion problem can be implemented using
shared variables

• Distributed systems:-
▫ Both the shared resources and the users may be
distributed, and shared memory does not exist
▫ Approaches based on message passing must be used.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 45

Mutual Exclusion: Requirements

• Freedom from deadlocks:
▫ Two or more sites should not endlessly wait on
conditions/messages that never become true/arrive.
• Freedom from starvation:
▫ No indefinite waiting.
• Fairness:
▫ Order of execution of CS follows the order of the
requests for CS. (equal priority).
• Fault tolerance:
▫ Recognize “faults”, reorganize, continue. (e.g., loss of
token).
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 46

Performance Measure
• Synchronization delay(sd),
▫ i.e., Time between the leaving of CS by a site and the
entry of CS by the next one: should be minimized.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 47

Performance Measure
• Response time:
▫ Time interval between request messages transmissions and exit of
CS.
• E the average CS execution time.
• System throughput,
▫ i.e., rate at which system executes requests for CS: should be
maximized.
▫ system throughput = 1 / (sd + E).

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 50

4 Marks
Classification of Mutual Exclusion Algorithms
1. Centralized approach
• There is single coordinator which handles all the requests to access
the shared data.
• Every process takes permission to the coordinator
2. Distributed approach
1. Non-token based:
• A site/process can enter a critical section when an assertion (condition) becomes
true.
• Algorithm should ensure that the assertion will be true in only one site/process.
2. Token based:
• A unique token (a known, PRIVILEGE message) is shared among cooperating
sites/processes.
• Possessor of the token has access to critical section.
• Need to take care of conditions such as
•loss of token,
•crash of token holder,
•possibility of multiple tokens, etc.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 51

8/10 Marks

Centralized approach
• One of the processes in the system is chosen to coordinate the entry
to the critical section
• A process that wants to enter its critical section sends a request
message to the coordinator
• The coordinator decides which process can enter the critical section
next, and its sends that process a reply message
• When the process receives a reply message from the coordinator, it
enters its critical section
• After exiting its critical section, the process sends a release message
to the coordinator and proceeds with its execution
• This scheme requires three messages per critical-section entry:
▫ request
▫ reply
▫ release

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 52

Centralized approach ……..(cont)

P2

3. Request

7. Release
6. Reply
9. Release
5. Release

P1 2. Reply Pc 8. Reply P3
1. Request
4. Request

P3 P2

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 53

Centralized approach ……..(cont)

• Advantages:
▫ Easy to implement
▫ Guaranteed Mutual Exclusion
▫ Request granted in order they are received
▫ No process ever wait forever (no starvation)

• Drawbacks.
▫ A single point of failure, the control site.
▫ the communication links near the control site are
likely to be congested and become a bottleneck.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 54

10 Marks
Distributed approach :-
Non-token Based Algorithms
• Notations:
▫ Si: Site i
▫ Ri: Request set, containing the ids of all Si’s from
which permission must be received before
accessing CS.
▫ Compose message containing:
 Identifier (machine ID, process ID)
 Name of resource
 Timestamp (totally-ordered Lamport)
▫ Send request to all processes in group

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 55

1. Lamport’s Algorithm

• Lamport’s Algorithm
▫ Ri = {S1, S2, …, Sn}, i.e., all sites.
▫ Request queue: maintained at each Si. Ordered by
time stamps.
▫ Assumption: message delivered in FIFO.

Ri:-[S1,S2,……Sn]
Si
Request queue:-((tsj, j), (tsi, i))

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 56

Lamport’s Algorithm
• Requesting CS :
▫ Site Si :Send REQUEST(tsi, i) message to all sites in its Ri.
Place REQUEST in request_queuei.
▫ Site Sj: On receiving the message; Sj sends time-stamped REPLY
message to si. Si’s request placed in request_queuej.

• Executing CS:
▫ Si has received a message with time stamp larger than (tsi,i) from
all other sites.
▫ Si’s request is the top most one in request_queuei.

• Releasing CS:
▫ Exiting CS: send a time stamped RELEASE message to all sites in
its request set.
▫ Receiving RELEASE message: Sj removes Si’s request from its
queue.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 57

Lamport’s Algorithm: Example

S1 (2,1)
Step 1:

S2
(1,2)
S3

S1 (1,2) (2,1)
Step 2:
S2 enters CS
S2
(1,2) (2,1)
S3 (1,2) (2,1)
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 58

Lamport’s Algorithm: Example…

(1,2) (2,1)
Step 3: S1

S2 leaves CS
S2
(1,2) (2,1)
S3
(1,2) (2,1)

S1 (1,2) (2,1) (2,1)

Step 4:
S1 enters CS
S2
(1,2) (2,1) (2,1)
S3
(1,2) (2,1) (2,1)
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 59

Lamport’s Algorithm
• Performance.
▫ 3(N-1) messages per CS invocation.
1. (N - 1) REQUEST
2. (N - 1) REPLY
3. (N - 1) RELEASE messages.
▫ Synchronization delay: T

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 60

10 Marks

2. Ricart-Agrawala Algorithm
• Distributed algorithm using reliable multicast
and logical clocks
• Process wants to enter critical section:
▫ Wait until everyone gives permission
▫ Enter critical section / use resource
• RD[i]:- Request Deferred vector
• Use two messages:
• REQUEST
• REPLY

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 61

Description of the Ricart-Agrawala

Algorithm
• Requesting the critical section:
a) When a site Si wants to enter the CS, it broadcasts a timestamped
REQUEST message to all other sites.
b) When site Sj receives a REQUEST message from site Si , it sends a
REPLY message to site Si
a) if site Sj is neither requesting nor executing the CS, or
b) if the site Sj is requesting and Si ’s request’s timestamp is smaller
than site Sj ’s own request’s timestamp.
c) Otherwise, the reply is deferred and Sj sets RDj [i]=1

• Executing the critical section:

c) Site Si enters the CS after it has received a REPLY message from
every site it sent a REQUEST message to.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 62

Description of the Ricart-Agrawala

Algorithm
• Releasing the critical section:
d) When site Si exits the CS, it sends all the deferred
REPLY messages: ∀j if RDi [j]=1, then send a
REPLY message to Sj and set RDi [j]=0.

• Notes:
▫ When a site receives a message, it updates its clock
using the timestamp in the message.
▫ When a site takes up a request for the CS for
processing, it updates its local clock and assigns a
timestamp to the request.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 63

Ricart-Agrawala: Example
Step 1:
S1 (2,1)

S2
(1,2)

S3
Step 2:
S1 (1,2) (2,1)

S2 enters CS
S2
(1,2) (2,1)

S3
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 64

Ricart-Agrawala: Example…

Step 3:
S1 CS

S1 enters CS
S2 CS
(2,1)

S3 S2 leaves CS

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 65

3. Maekawa’s Algorithm ...

Setup
 The intersection of any two voting sets is non-empty
 M1: (∀i ∀j : i ≠ j, 1 ≤ i, j ≤ N :: Vi ∩ Vj ≠ φ)
 Each process belongs to its own voting set
 M2: (∀i : 1 ≤ i ≤ N :: Si ∈ Vi)
 Each voting set is of size K
 M3: (∀i : 1 ≤ i ≤ N :: |Vi | = K)
 Maekawa showed that K=N works best
 Each process pi is associated with a voting set Vi (of
processes)
 M4: Any site Sj is contained in K number of Vi’s, 1 ≤ i, j
≤ N.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 66

Maekawa’s Algorithm ...

Maekawa Voting Set with N=4
p1’s voting set = v1 v2

p1 p2

p3 p4

v3 v4

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 67

Request Subsets
• Example k = 2; (N = 3).
▫ R1 = {1, 2}; R3 = {1, 3}; R2 = {2, 3}
• Example k = 3; N = 7.
▫ R1 = {1, 2, 3}; R4 = {1, 4, 5}; R6 = {1, 6, 7};
▫ R2 = {2, 4, 6}; R5 = {2, 5, 7}; R7 = {3, 4, 7};
▫ R3 = {3, 5, 6}

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 68

Maekawa’s Algorithm ... p1 p2

p3 p4
Protocol
 Each process pi is associated with a voting set Vi
(of processes)

To access a critical section, pi requests permission

from all other processes in its own voting set Vi

Voting set member gives permission to only one

requestor at a time, and queues all other requests

Guarantees safety
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 69

Maekawa’s Algorithm ...

• Requesting CS
▫ Si sends REQUEST(i) to sites in Vi.
▫ Sj sends REPLY to Si if
 Sj has NOT sent a REPLY message to any site after it
received the last RELEASE message.
 Otherwise, queue up Si’s request.
p1 p2
• Executing CS:
p3
• after getting REPLY from all sites in Vi. p4

• Releasing CS
▫ Send RELEASE(i) to all sites in Vi
▫ Any Sj after receiving RELEASE message, send REPLY
message to the next request in queue.
▫ If queue empty, update status indicating receipt of RELEASE.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 70

Maekawa’s Algorithm ...

• On initialization
state := RELEASED;
voted := FALSE;
• For pi to enter the critical section
state := WANTED;
Multicast request to all processes in Vi – {pi};
Wait until (number of replies received = (K – 1));
state := HELD;
• On receipt of a request from pi at pj (i ≠ j)
if (state = HELD or voted = TRUE)
then
queue request from pi without replying;
else
send reply to pi;
voted := TRUE;
end if
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 71

Maekawa’s Algorithm ...

• For pi to exit the critical section
state := RELEASED;
Multicast release to all processes in Vi – {pi};
• On receipt of a release from pi at pj (i ≠ j)
if (queue of requests is non-empty)
then
remove head of queue – from pk, say;
send reply to pk;
voted := TRUE;
else
voted := FALSE;
end if

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 73

10 Marks

Token-based Algorithms
• Unique token circulates among the participating sites.
• A site can enter CS if it has the token.
• Token-based approaches use sequence numbers instead
of time stamps.
▫ Request for a token contains a sequence number.
▫ Sequence number of sites advance independently.
▫ Sequence no. is incremented when site request for a token
• Correctness issue is minor since only one token is
present -> only one site can enter CS.
• Deadlock and starvation issues to be addressed.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 74

1. Suzuki-Kasami broadcast Algorithm

• If a site without a token needs to enter a CS, broadcast a
REQUEST for token to all other sites.

• Data structure used

▫ Token:
(a) Q:-Queue of request sites
(b) Array LN[1..N]:- the sequence number of the most recent
execution by a site j.
▫ RNi[1…n] : request queue maintained at each site Si of size n

• Token holder sends token to requestor, if it is not inside CS.

Otherwise, sends after exiting CS.
• Token holder can make multiple CS accesses.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 75

Suzuki-Kasami broadcast Algorithm

• Design issues:
▫ Distinguishing outdated REQUEST messages.
 Format: REQUEST(j,n) -> jth site making nth request.
 Each site has RNi[1..N] -> RNi [j] is the largest sequence
number of received from j
(i.e. RNi [j]=max(RNi [j],n)
 Test RNi[j]>n for outdated message.

▫ Determining which site has an outstanding token

request.
 If LN[j] = RNi [j] - 1, then Sj has an outstanding request.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 76

Suzuki-Kasami broadcast Algorithm ...

• Requesting the critical section
▫ If the requesting process does not have the token, it increments its
sequence number RNi[i], and sends a REQUEST(i, n) message to all
other sites
▫ When a site Sj receives this message, it sets
RNj[i] =max(RNj [i], n).
If Sj has the idle token, then it sends the token to Si if LN[i]=RNj[i]-1

• Executing the CS
▫ Site Si executes the CS when it has received the token

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 77

Suzuki-Kasami broadcast Algorithm ...

• Releasing CS (Passing the token)
▫ After finishing CS
▫ (assuming Si has token), LN[i] := RNi[i]
▫ Token holder checks if RNi[j] = LN[j] + 1. If so, place j
in Q.
▫ Send token to the site at head of Q.
• Performance
▫ 0 to N messages per CS invocation.
▫ Synchronization delay is 0 (if the token holder repeats
CS) or T.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 78

Suzuki-Kasami: Example
Step 1: S1 has token, S3 is in queue
Site Seq. Vector RN Token Vect. LN Token Queue
S1 10, 15, 9 10, 15, 8 3
S2 10, 16, 9
S3 10, 15, 9
Step 2: S3 gets token, S2 in queue
Site Seq. Vector RN Token Vect. LN Token Queue
S1 10, 16, 9
S2 10, 16, 9
S3 10, 16, 9 10, 15, 9 2
Step 3: S2 gets token, queue empty
Site Seq. Vector RN Token Vect. LN Token Queue
S1 10, 16, 9
S2 10, 16, 9 10, 16, 9 <empty>
S3 10, 16, 9
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 79

10 Marks

4. Raymond’s Algorithm
• Sites are arranged in a logical directed tree. Root: token
holder. Edges: directed towards root.
• Every site has a variable holder that points to an
immediate neighbor node, on the directed path towards
root. (Root’s holder point to itself).
Request queue
S1

Request queue S2 S3

S4 S5 S6 S7

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 80

Raymond’s Algorithm
• Requesting CS
▫ If Si does not hold token and request CS, sends REQUEST
upwards provided its request_q is empty. It then adds its
request to request_q.
▫ Non-empty request_q -> REQUEST message for top entry in q
(if not done before).
▫ Site on path to root receiving REQUEST -> propagate it up, if its
request_q is empty. Add request to request_q.
▫ Root on receiving REQUEST -> send token to the site that
forwarded the message. Set holder to that forwarding site.
▫ Any Si receiving token -> delete top entry from request_q, send
token to that site, set holder to point to it. If request_q is non-
empty now, send REQUEST message to the holder site.
• Executing CS:
▫ getting token with the site at the top of request_q. Delete top of
request_q, enter CS.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 81

Raymond’s Algorithm …
• Releasing CS
▫ If request_q is non-empty, delete top entry from q, send token
to that site, set holder to that site.
▫ If request_q is non-empty now, send REQUEST message to the
holder site.
• Performance
▫ Average messages: O(log N) as average distance between 2
nodes in the tree is O(log N).
▫ Synchronization delay: (T log N) / 2, as average distance
between 2 sites to successively execute CS is (log N) / 2.
▫ Greedy approach: Intermediate site getting the token may enter
CS instead of forwarding it down. Affects fairness, may cause
starvation.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 82

Raymond’s Algorithm: Example

Step 1: Token
S1 holder

S2 Token S3
request
S4 S5 S6 S7

Step 2:
S1

S2 Token S3

S4 S5 S6 S7
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 83

Raymond’s Algm.: Example…

Step 3:
S1

S2 S3

S4 S5 S6 S7

Token
holder

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 84

Comparison
Non-Token Resp. Time(ll) Sync. Delay Messages(ll) Messages(hl)

Lamport 2T+E T 3(N-1) 3(N-1)

Token Resp. Time(ll) Sync. Delay Messages(ll) Messages(hl)

Suzuki-Kasami 2T+E T N N
Raymond T(log N)+E Tlog(N)/2 log(N) 4

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

Distributed deadlock
 86

Introduction

• A process must request a resource

before using it, and must release the
resource after finishing with it.
• Resource: something a process uses
▫ Usually limited (at least somewhat)
• Examples of computer resources
▫ Printers
▫ Semaphores / locks
▫ Tables (in a database)
• Processes need access to resources in reasonable order

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 87

What is a deadlock?
• Formal definition:
“A set of processes is deadlocked if each process in
the set is waiting for an event that only another
process in the set can cause.”
• Usually, the event is release of a currently held
resource
• In deadlock, none of the processes can
▫ Run
▫ Release resources
▫ Be awakened

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 88

When do deadlocks happen?

Suppose
▫ Process 1 holds resource A
and requests resource B Process 1 Process 2
▫ Process 2 holds B and
requests A A B
▫ Both can be blocked, with
neither able to proceed
A
Deadlocks occur when
… B
▫ Processes are granted
exclusive access to devices DEADLOCK!
or software constructs
(resources)
▫ Each deadlocked process
needs a resource held by
another deadlocked process
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 89

Necessary conditions for

deadlock
• Mutual exclusion
▫ Each resource is assigned to at most one process
• Hold and wait
▫ A process holding resources can request more resources
• No preemption
▫ Previously granted resources cannot be forcibly taken away
• Circular wait
▫ There must be a circular chain of 2 or more processes where each is
waiting for a resource held by the next member of the chain

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 90

Types of Deadlocks in Distributed

Systems
• Resource Deadlock
 Most Common.
 Occurs due to lack of requested Resource.

• Communication Deadlock
 A Process waits for certain messages before it can
proceed.
Two processes exchange a long message with each other,
but their socket buffer is smaller than the message.

Process message message Process

A B

Socket Socket
buffer buffer
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
 91

AND, OR Models
• AND Model
▫ A process/transaction can simultaneously request for multiple
resources.
▫ Remains blocked until it is granted all of the requested
resources.

• OR Model
▫ A process/transaction can simultaneously request for multiple
resources.
▫ Remains blocked till any one of the requested resource is
granted.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 92

Deadlock modeling
b
• Deadlocks can be modeled using the
directed graphs. a c
• Some terminologies:
▫ directed graph: A directed graph is a pair (N,E),where
N-nonempty set of nodes,
f d
E-set of directed edges.
▫ Path:(a,b,c,….f) e
▫ Cycle: it is a path whose first and last
nodes are the same.
▫ reachable set: a path exists from a to b.
▫ knot: a knot contains one/more cycles.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 93

RESOURCE ALLOCATION GRAPH

A visual ( mathematical ) way to determine if a deadlock has, or may occur.
G = ( V, E ) The graph contains nodes and edges.
V Nodes consist of processes = { P1, P2, P3, ...} and resource
types { R1, R2, ...}
E Edges are ( Pi, Rj ) or ( Ri, Pj )
• Process is a circle, resource type is square; dots represent number of
instances of resource in type. Request points to square, assignment
comes from dot
• An arrow from the process to resource indicates the process is
requesting the resource.
• An arrow from resource to process shows an instance of the resource
has been allocated to the process.

Pi Pi
Pi
Rj Rj

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 95

RESOURCE ALLOCATION GRAPH

• If the graph contains no cycles, then no process is deadlocked.
• If there is a cycle, then:
a) If resource types have multiple instances, then deadlock
MAY exist.
b) If each resource type has 1 instance, then deadlock has
occurred.
R1 R3
R3 Assigned to P3
Resource allocation graph

P1 P2 P3
P2 Requests R3

R2 R4

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 96

RESOURCE ALLOCATION GRAPH …...(cont)

Wait-for graph

Resource allocation graph Resource allocation graph

with a deadlock. with a cycle but no deadlock.
R1 R3
R1
P2

P1 P2 P3 P1 P3

R4
R2 R2

P4

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 97

Wait-for graph
• Used to represent the waiting relationships between current
transactions.
• In a wait-for graph the nodes represent transactions and
the edges represent wait for relationships between
transactions.
• P1 -> P2 implies P1 is waiting for a resource from P2.
• Transaction-wait-for Graphs (TWF): WFG in databases.
P2
P1

P3

P5
P4

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 98

Control Organization for Deadlock

Detection
Centralized Deadlock Detection
Distributed Deadlock Detection
Hierarchical Deadlock Detection

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 99

Centralized Deadlock Detection

▫ One control node (Coordinator) maintains
Global WFG and searches for cycles.
▫ Advantage:
 Simple and easy to implement
▫ Drawback:
 Single point of failure
 Bottleneck

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 100

Distributed Deadlock Detection

▫ Each node equally responsible in maintaining
Global WFG and detecting Deadlocks.
▫ Drawback:
 Difficult to design (no global shared
memory)
 Several site can initiate deadlock detection
for the same site
 Several site can detect same deadlock

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 101

Hierarchical Deadlock Detection

▫ Nodes organized in a tree, where each

site detects deadlocks involving only its
descendants.

▫ Drawback:
 Need special care while arranging the
site in a hierarchy.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 102

Deadlock Detection Algorithms

• Centralized Deadlock Detection
▫ Complete centralized algorithm
▫ Ho-Ramamoorthy’s one and two phase
algorithms.
• Distributed Deadlock Detection
▫ Chandy-Misra-Haas Edge Chasing algorithm.

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 103

Completely Centralized Deadlock

Detection Algorithm
• Functions of Control site
▫ Maintains the WFG
▫ Resources are controlled by sending “resource request”
and “resource release” messages to the control site
▫ Updates are done in WFG according to the request
Machine 0 Machine 1 Coordinator

Holds Wants
A S S C A S C
Wants
Holds
R R
Holds T T
B B

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 104

Completely Centralized Deadlock

Detection Algorithm

• Advantage-
▫ Simple and easy

• Disadvantages-
▫ Single point of failure
▫ Network congestion issues
▫ False deadlock detection (Phantom Deadlocks)

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 105

Phantom Deadlocks

P0 R P2
System A System B

S P1 T

 P1 releases resource S and asks-for resource T.

 2 Messages sent to Control Site:
1. Releasing S.
2. Waiting-for T.
 Message 2 arrives at Control Site first. Control Site
makes a WFG with cycle, detecting a phantom
deadlock.
Kanchan K. Doke, Computer Engg. Dept. ,BVCOE
Total Centralized Control (cont)
• The Ho-Ramamoorthy Algorithms
▫ Two phase (can be for AND or OR model)
 Each site has a status( of process) table of locked and
waited resources
 The control site will periodically ask for this table from
each node
 The control node will search for cycles and, if found,
will request the table again from each node
 Only the information common in both reports will be
analyzed for confirmation of a cycle

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 107

Total Centralized Control (cont)

• The Ho-Ramamoorthy Algorithms (cont)
▫ One phase (can be for AND or OR model)
 Each site keeps 2 tables; process status and resource
status
 The control site will periodically ask for these tables
(both together in a single message) from each node
 The control site will then build and analyze the WFG,
looking for cycles by considering only matched
entries of both the tables
 Advantage:-faster
 Disadvantage:- required more storage

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 108

Distributed Deadlock Detection

Algorithms
• Each node has the same responsibility for, and will
expend the same amount of effort in detecting
deadlock
▫ The WFG becomes an abstraction, with any single node
knowing just some small part of it

▫ Generally detection is launched from a site when some

thread at that site has been waiting for a “long” time in a
resource request message

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

Edge-Chasing Algorithm
• Chandy-Misra-Haas’s Algorithm (AND MODEL):
▫ A probe(i, j, k) is initiated by a deadlock detection process
Pi. This probe is sent by the home site of Pj to Pk.
▫ Probe message is circulated via the edges of the graph.
Probe returning to Pi implies deadlock detection.

▫ Terms used:
 Pj is dependent on Pk, if a sequence of Pj, Pi1,.., Pim, Pk exists.
 Pj is locally dependent on Pk, if above condition + Pj,Pk on same
site.
 Each process maintains an array dependenti:
dependenti (j)= true ….. if Pj is dependent on Pi
(initially set to false for all i & j).

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 110

Chandy-Misra-Haas’s Algorithm
Sending the probe:
if Pi is locally dependent on itself then deadlock.
else for all Pj and Pk such that
(a) Pi is locally dependent upon Pj, and
(b) Pj is waiting on Pk, and
(c ) Pj and Pk are on different sites, send probe(i,j,k) to the home
site of Pk.

Receiving the probe:

if (d) Pk is blocked, and
(e) dependentk(i) is false, and
(f) Pk has not replied to all requests of Pj,
then begin
dependentk (i) := true;
if k = i then Pi is deadlocked
else ...

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 111

Chandy-Misra-Haas’s Algorithm
Receiving the probe:
…….
else for all Pm and Pn such that
(a’) Pk is locally dependent upon Pm, and
(b’) Pm is waiting on Pn, and
(c’) Pm and Pn are on different sites, send probe(i,m,n)
to the home site of Pn.
end.

Performance:
• For a deadlock that spans m processes over n sites, m(n-1)/2
messages are needed.
• Size of the message 3 words.
• Delay in deadlock detection O(n).

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 112

Chandy-Misra-Haas’s Algorithm

( 1,7,1 )

Site 3

P1 P2 P6 P7

( 1,2,3 )
( 1,5,6 )
Site 1
( 1,2,4 ) Site 2

P3

P1 initiates Deadlock
P4 P5
Detection

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE

 113

Kanchan K. Doke, Computer Engg. Dept. ,BVCOE