Chapter - 3

Synchronization

© Oxford University Press 2011

 Topics
• Clock synchronization
• Physical clock
• Logical clocks
• Election algorithms

• Distributed Mutual exclusion

• Requirement of mutual exclusion algorithm
• Performance Measure

• Non- token Based Algorithms: Lamport, Ricart–Agrawala‘s and

Maekawa‘s Algorithms; Token-based Algorithms: Suzuki-Kasami‘s
Broadcast Algorithms and Raymond‘s Tree-based Algorithm; and
Comparative Performance Analysis.

• Deadlocks in distributed systems

© Oxford University Press 2011

 Introduction

© Oxford University Press 2011

 Introduction
• A distributed system consists of many
processors running either one or multiple
processes concurrently.
• It is economical to share system resources
such as hardware and software among
concurrently executing processes.
• The sharing can happen in either co-operative
or competitive modes since the system has a
limited number of resources.
© Oxford University Press 2011
• For example, a resource such as a printer or a
scanner cannot be used by multiple processes
simultaneously.
• So it must wait for one process to complete
using it and then take up the next.
• Cooperating and competitive processes need
to follow a set of guidelines that guarantee
correct interaction between them.
• These rules for enforcing correct interactions
are implemented in the form of
synchronization mechanisms.
© Oxford University Press 2011
Clock synchronization

© Oxford University Press 2011

 Clock synchronization
• Ordering of events taking place in processes of
a distributed system according to their
temporal association.

• Required to ensure mutual exclusion to

guarantee serialization of concurrent access to
shared resources.

© Oxford University Press 2011

 1. Christian’s Algorithm
• To keep absolute time, Christian's algorithm
proposes the concept of a time server,
typically a UTC (Coordinated universal time)
server.
• The machines are periodically expected to
make an RPC (Remote ProcedureCall) to
obtain time from this server.
• A machine adjusts its time according to the
following algorithm.
© Oxford University Press 2011
 Christian’s Algorithm(conti…)
• Let T0 be local system time at which the
request is sent by process P of a node, and T₁
be time at which the response is received at P.
• Round trip delay time (RTT) = T1- T0
• The estimated overhead due to the network
delay in each direction is then
(T1 - T0) / 2

© Oxford University Press 2011

• The new time Tp at P can be set to the time
returned by the server plus the time that
elapsed since the server generated the
timestamp, that is,
Tp : Ts + (T1- T0) / 2
• For example, if T0= 19 and T1 = 27 then
(RTT)/2 = 8/2 = 4

• If Ts, is 16, then Tp = 16 + 4 = 20 will be

absolute clock time adjusted at process P

© Oxford University Press 2011

Christian’ Algorithm(conti…)

© Oxford University Press 2011

Christian’s Algorithm(conti…)
Uses a time server to synchronize clocks

Mainly designed for LAN

Time server keeps the reference time (UTC-Universal Coordinated
Time)

A client asks the time server for time, the server responds
with its current time T, and the client uses the received
value T to set its clock

But network round-trip time introduces an error

RTT = response received time – request sent time
(measurable at client)
© Oxford University Press 2011
 2. Berkeley’s Algorithm
• The Berkeley algorithm, developed by Gusella
and Zatti, assumes that none of the nodes
have an accurate time source.
• Thus, it averages the time and synchronizes
all.
• It works in the master-slave configuration.
• The server polls each machine periodically,
asking for their time.

© Oxford University Press 2011

• The time at each machine may be estimated by using
Christian's method to account for network delays.

• When all results are in, the master computes the

average time (including its own time in the
calculation).

• Instead of sending the updated time back to slaves,

which would introduce further uncertainty due to
network delays, it sends each machine the offset by
which clocks need adjustment.

• The clocks at slaves are then adjusted according the

offset.
© Oxford University Press 2011
• Three machines have times 3:00, 3:25 and
2:50.
• The master is with the time 3:00.
• It polls the slaves and sends out a synchro-
nization query to other nodes.
• Each of these machines sends a timestamp
difference as a query response.

© Oxford University Press 2011

• The server now averages the three
timestamps - the two it received and its
own-computing
(25-10+ 0)/3 = 5.
• It sends an offset
(e.g., for slave offset = 5-(-10) = 15)
to each slave so that the slave's time will be
synchronized to the average after the offset is
applied and new I will be calculated.

• The server has to adjust its own time by 0:05.

© Oxford University Press 2011
Berkeley’s Algorithm

© Oxford University Press 2011

Berkeley’s Algorithm

© Oxford University Press 2011

 Network Time Protocol
• Network Time Protocol (NTP) is the standard
followed to synchronize clocks on the Internet.
• NTP synchronizes all participating computers
to within a few milliseconds of Coordinated
Universal Time (UTC).
• The standard uses a tree structure to organize
the NTP servers as shown in Fig. 7.3(a).

© Oxford University Press 2011

© Oxford University Press 2011
• The structure is a hierarchical structure.
• Each node requires synchronizing with its
parent node.
• It is implemented as a client-server protocol.
• UDP (User Datagram Protocol) port 123 is
reserved for NTP server.

© Oxford University Press 2011

• Algorithm

• For RTT calculation

RTT = (T3-T0)-(T2-T1); *Time spend in the network"/
• For Offset calculation
O=((T1-T0)+(T3-T2))/2
• Once the offset and RTT are calculated, the
client clock is adjusted to reduce the offset.

© Oxford University Press 2011

 Logical Clock

© Oxford University Press 2011

• Logical clock assigns timestamp (sequence
number) to events for sequencing them in the
order agreed upon by all processes.

• This timestamp is not the absolute time, but

the agreed upon relation amongst the events.

• This timestamp style event ordering is termed

as logical clock.

© Oxford University Press 2011

 Logical Clock- Lamport(1978)
• If two processes do not interact, it is not
necessary that their clocks be synchronized
because the lack of synchronization would not
be observable, so it will not cause problems

• All processes need to agree on the order in

which events occur

© Oxford University Press 2011

• Leslie Lamport established "happened before"
relationship between events as depicted in
Fig.

© Oxford University Press 2011

© Oxford University Press 2011
 Logical Clocks
• Why Logical Clocks?
It is difficult to utilize physical clocks to order events uniquely
in distributed systems.
▪ Logical clock assigns timestamp(sequence number) to events
for sequencing them in the order agreed upon by all
processes.
• The essence of logical clocks is based on the happened-before
relationship presented by Lamport.

© Oxford University Press 2011

 Happen-Before Relationship
• Happened before relation ( casual ordering)
– If a and b are events in the same process, and a occurs before
b then a→ b is true.

– 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 is also true.

– If a → b and b → c, then a → c (transitive).

– Concurrent Events - events a and b are concurrent (a||b) if

neither a! → b nor b !→ a is true.

© Oxford University Press 2011

 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).

© Oxford University Press 2011

 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.

© Oxford University Press 2011

© Oxford University Press 2011
© Oxford University Press 2011
 Mutual Exclusion
• In 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.

© Oxford University Press 2011

© Oxford University Press 2011
 Performance metrics of mutual
exclusion.
• Synchronization delay: Time interval between CR exit and
new entry by any process.
• System Throughput: Rate at which requests for the CR get
executed.
• Message complexity: Number of messages that are required
per CR execution by a process.
• Response time: Time interval from a request send to its CR
execution completed.

© Oxford University Press 2011

 Election Algorithms

• Many distributed algorithms employ a coordinator process that

performs functions needed by the other processes in the
system
– enforcing mutual exclusion
– maintaining a global wait-for graph for deadlock detection
– replacing a lost token
– controlling an input/output device in the system

• If the coordinator process fails due to the failure of the site at

which it resides, a new coordinator must be selected through
an election algorithm.

© Oxford University Press 2011

 Solution – an Election
• All processes currently involved get together
to choose a coordinator
• If the coordinator crashes or becomes
isolated, elect a new coordinator
• If a previously crashed or isolated process,
comes on line, a new election may have to be
held

38
© Oxford University Press 2011
■ A process begins an election when it notices,
through timeouts, that the coordinator has failed.

■ Three types of messages

■ An election message is sent to announce an
election.

■ An ok message is sent in response to an

election message.

■ A coordinator message is sent to announce the

identity of the elected process (the “new
coordinator”).
© Oxford University Press 2011
 The Bully Election Algorithm
(Cont.)
• The process that knows it has the highest identifier can elect itself as the
coordinator simply by sending a coordinator message to all processes
with lower identifiers.

• A process with lower identifier begins an election by sending an election

message to those processes that have a higher identifier and awaits an
ok message in response.
– If none arrives within time T, the process considers itself the
coordinator and sends a coordinator message to all processes with
lower identifiers.
– If a reply arrives, the process waits a further period T’ for a
coordinator message to arrive from the new coordinator. If none
arrives, it begins another election.

© Oxford University Press 2011

 The Bully Election Algorithm
(Cont.)
• If a process receives an election message, it
sends back an ok message and begins another
election (unless it has begun one already).

• If a process receives a coordinator message, it

sets its variable coordinator-id to the
identifier of the coordinator contained within
it.

© Oxford University Press 2011

 The Bully Election Algorithm
•
(Cont.)
What happens if a crashed process recovers and
immediately initiates an election?

• If it has the highest process identifier (for example P7 in

previous slide), then it will decide that it is the coordinator
and may choose to announce this to other processes.
– It will become the coordinator, even though the current
coordinator is functioning (hence the name “bully”)
– This may take place concurrently with the sending of
coordinator message by another process which has previously
detected the crash.

© Oxford University Press 2011

© Oxford University Press 2011
© Oxford University Press 2011
The Bully Algorithm

© Oxford University Press 2011

The Bully Algorithm

© Oxford University Press 2011

 Ring Algorithm
• All processed organized in ring
• Independent of process number
• Suppose P notices no coordinator
• Sends election message to successor with own process
number in body of message
• (If successor is down, skip to next process, etc.)
• Suppose Q receives an election message
• Adds own process number to list in message body
•…

Election Algorithms
© Oxford University Press 2011 47
 Ring Election Algorithms
• Suppose P receives an election message with
its own process number in body
• Changes message to coordinator message, preserving
body
• All processes recognize highest numbered process as
new coordinator
• If multiple messages circulate …
• …they will all contain same list of processes
(eventually)
• If process comes back on-line
• Calls new election

© Oxford University Press 2011 48

 Ring Algorithm: Example

Initiation:
[Link] 4 sends an ELECTION message to its successor (or next alive
process) with its ID
[Link] process adds its own ID and forwards the ELECTION
message
Leader Election:
3. Message comes back to initiator, here the initiator is 4.
4. Initiator announces the Press
© Oxford University winner
2011by sending another message
Ring Algorithm

© Oxford University Press 2011

Ring Algorithm

© Oxford University Press 2011

 Distributed Mutual Exclusion
• Assumptions (DME)
– The system consists of n processes; each process Pi
resides at a different processor.

• The application-level protocol for executing a critical section

proceeds as follows:
– Enter() : enter critical section (CS/CR)
– ResourceAccess(): access shared resources in CS
– Exit(): Leave CS – other processes may now enter.

© Oxford University Press 2011

 DME: The Centralized Server Algorithm

• 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 it 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.

© Oxford University Press 2011

 Mutual Exclusion:
A Centralized Algorithm

a) Process 1 asks the coordinator for permission to enter a critical region. Permission is
granted
b) Process 2 then asks permission to enter the same critical region. The coordinator
does not reply.
c) When process 1 exits the critical region, it tells the coordinator, coordiinator then
replies to 2

© Oxford University Press 2011

 A Centralized Algorithm

coordinator
process Request
Grant

Enter crical Release

section

• Advantages: It is fair, easy to implement, and requires only three messages

Exit
per use of a critical region (request, grant, release).
• Disadvantages: single point of failure.

© Oxford University Press 2011

 Decentralized algorithm
• When process wants to access the resource , it
will simply need to get a majority vote from
m>n/2 coordinators
• Less vulnerable to failures of single
coordinator
• If permission to access the resource is denied
i.e if process get less than m votes
• It is assumed that it will back off for
randomly-chosen time, will try later
© Oxford University Press 2011
 Decentralized Algorithm
• The problem with this scheme is that if many
nodes want to access the same resource, it
turns out that the utilization rapidly drops
• There are many nodes competing to get
access that eventually no one is able to get
enough votes leaving the resource unused

© Oxford University Press 2011

Distributed Algorithm

© Oxford University Press 2011

© Oxford University Press 2011
 Token Ring

© Oxford University Press 2011

© Oxford University Press 2011
 Distributed Mutual Exclusion Algorithms
• 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.
• Token based:
• A unique token (a known, unique 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.

© Oxford University Press 2011 62

 Non-token Based Algorithms
• Notations:
– Si: SiteI/ Nodes
– Ri: Request set, containing the ids of all Sis from which permission
must be received before accessing CS.
– Non-token based approaches use time stamps to order requests
for CS.
– Smaller time stamps get priority over larger ones.
• Lamport’s Algorithm
– Ri = {S1, S2, …, Sn}, i.e., all sites. Or nodes
– Request queue: maintained at each Si. Ordered by time stamps.
– Assumption: message delivered in FIFO.

© Oxford University Press 2011 63

Classification of Mutual Exclusion
Algorithms

• Centralized mutual exclusion algorithms

• Decentralized mutual exclusion algorithms
• Distributed mutual exclusion algorithms
• Token Ring mutual exclusion algorithm

© Oxford University Press 2011

 Classification of Distributed
Mutual Exclusion Algorithms
• Non-token-based algorithm:
• Lamport’s Distributed Mutual Algorithm
• Ricart–Agrawala Algorithm
• Maekawa’s Algorithm

• Token-based algorithm:
• Suzuki–Kasami’s Broadcast Algorithm
• Singhal’s Heuristic Algorithm
• Raymond’s Tree-Based Algorithm

© Oxford University Press 2011

 Lamport’s Algorithm for mutual
exclusion
• Requesting CS:
– Send REQUEST(tsi, i). (tsi,i): Request time stamp. Place REQUEST in
request_queuei.
– 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.

© Oxford University Press 2011 66

Lamport’s Distributed Mutual
Exclusion Algorithm

© Oxford University Press 2011

 Lamport’s Algorithm: 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
(1,2) (2,1)
© Oxford University Press 2011 68
 Performance Parameters
• Lamport’s algorithm has message overhead of total 3(N −
1) messages: N – 1 REQUEST messages to All process (N minus
itself), N −1 REPLY messages, and N −1 RELEASE messages per
CR invocation.

• The synchronization delay is T. Throughput is 1/(T + E).

• The algorithm has been proven to be fair and correct. It can

also be optimized by reducing the number of RELEASE
messages sent.

© Oxford University Press 2011

 Ricart-Agrawala Algorithm
• Requesting critical section
– Si sends time stamped REQUEST message
– Sj sends REPLY to Si, if
• Sj is not requesting nor executing CS
• If Sj is requesting CS and Si’s time stamp is smaller than its
own request.
• Request is deferred otherwise.
• Executing CS: after it has received REPLY from all sites in
its request set.
• Releasing CS: Send REPLY to all deferred requests.

© Oxford University Press 2011 70

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

S2
(1,2)

S3

Step 2:
S1

S2 enters CS
S2

(2,1)
S3

© Oxford University Press 2011 71

 Ricart-Agrawala: Example…

Step 3:
S1

S1 enters CS
S2

(2,1)
S2 leaves CS
S3

© Oxford University Press 2011 72

 Ricart-Agrawala:
• The algorithm does not use explicit RELEASE
message. The dequeuing is done on the receipt of
REPLY itself. Thus, total message overhead would be
2(N − 1) messages, that is, for entering a CR, (N − 1)
requests and exiting (N − 1) replies.

• 2. The failure of any process almost halts the

algorithm (recovery measures are needed) as it
requires all replies.

© Oxford University Press 2011

 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).
• 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.

B. Prabhakaran
© Oxford University Press 2011 74
 Raymond’s Algorithm …
• Executing CS: getting token with the site at
the top of request_q. Delete top of
request_q, enter CS.
• 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.

B. Prabhakaran
© Oxford University Press 2011 75
Raymond’s Algorithm: Example
Step 1: Token
S
holder
1

S Token S
2 request 3

S S S6 S
4 5 7
Step 2:
S
1

S S
2 Token 3

S S S6 S
4 5 7
B. Prabhakaran
© Oxford University Press 2011 76
Raymond’s Algm.: Example…
Step 3:
S
1

S S
2 3

S S S6 S
4 5 7
Token
holder

B. Prabhakaran
© Oxford University Press 2011 77
 Suzuki-Kasami Algorithm
• If a site without a token needs to enter a CS, broadcast a
REQUEST for token message to all other sites.
• Token: (a) Queue of request sites (b) Array LN[1..N], the
sequence number of the most recent execution by a site j.
• Token holder sends token to requestor, if it is not inside
CS. Otherwise, sends after exiting CS.
• Token holder can make multiple CS accesses.
• 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 request from j.
– Determining which site has an outstanding token request.
• If LN[j] = RNi[j] - 1, then Sj has an outstanding request.
B. Prabhakaran
© Oxford University Press 2011 78
 Suzuki-Kasami Algorithm ...
• Passing the token
– After finishing CS
– (assuming Si has token), LN[i] := RNi[i]
– Token consists of Q and LN. Q is a queue of
requesting sites.
– Token holder checks if RNi[j] = LN[j] + 1. If so,
place j in Q.
– Send token to the site at head of Q.

B. Prabhakaran
© Oxford University Press 2011 79
■ Suzuki-Kasami algorithm
■ Completely connected network of processes

■ There is one token in the network. The owner of

the token has the permission to enter CS.

■ Token will move from one process to another

based on demand.

© Oxford University Press 2011

 Suzuki-Kasami Algorithm
■ When a process i receives a request (i, num) from
process k, it sets req[k] to max(req[k], num) and
enqueues the request in its Q

■ When process i sends a token to the head of Q,

■ it sets last[i] := its own num, and passes the array
last, as well as the tail of Q,

Req: array[0..n-1] of integer

Last: Array [0..n-1] of integer

© Oxford University Press 2011 81

Example
req=[1,0,0,0,
req=[1,0,0,0,0 0]
] 1
last=[0,0,0,0,0 0
]

2
req=[1,0,0,0,
0]
4
req=[1,0,0,0,
0] 3
req=[1,0,0,0,
0]

initial state

© Oxford University Press 2011 82

Example
req=[1,1,1,0
req=[1,1,1,0,0 ,0]
] 1
last=[0,0,0,0,0 0
]

2
req=[1,1,1,0
,0]
4
req=[1,1,1,0
,0] 3
req=[1,1,1,0
,0]

1 & 2 send requests

© Oxford University Press 2011 83

Example
req=[1,1,1,0,
req=[1,1,1,0,0 0]
] 1
last=[1,0,0,0, 0
0]
Q=(1,2)

2
req=[1,1,1,0
,0]
4
req=[1,1,1,0
,0] 3
req=[1,1,1,0
,0]

0 prepares to exit CS

© Oxford University Press 2011 84

Example
req=[1,1,1,0
req=[1,1,1,0, ,0]
0] 1 last=[1,0,0,0
0 ,0]
Q=(2)

2
req=[1,1,1,0
,0]
4
req=[1,1,1,0
,0] 3
req=[1,1,1,0
,0]

0 passes token (Q and last) to 1

© Oxford University Press 2011 85

Example
req=[2,1,1,1,0
req=[2,1,1,1,0] ]
1 last=[1,0,0,0,
0 0]
Q=(2,0,3)

2
req=[2,1,1,1,
0]
4
req=[2,1,1,1,
0] 3
req=[2,1,1,1,
0]

0 and 3 send requests

© Oxford University Press 2011 86

Example
req=[2,1,1,1,
req=[2,1,1,1, 0]
0] 1
0

2
req=[2,1,1,1,
0]
4
last=[1,1,0,0,
req=[2,1,1,1,
0] 3 0]
Q=(0,3)
req=[2,1,1,1,
0]

1 sends token to 2

© Oxford University Press 2011 87

 Singhal’s Heuristic token based
algorithm
• Instead of broadcast: each site maintains information on other sites, guess
the sites likely to have the token.
• Data Structures:
– Si maintains SVi[1..M] and SNi[1..M] for storing information on other sites:
state and highest sequence number.
– Token contains 2 arrays: TSV[1..M] and TSN[1..M].
– States of a site
• R : requesting CS
• E : executing CS
• H : Holding token, idle
• N : None of the above
– Initialization:
• SVi[j] := N, for j = M .. i; SVi[j] := R, for j = i-1 .. 1; SNi[j] := 0, j = 1..N. S1
(Site 1) is in state H.
• Token: TSV[j] := N & TSN[j] := 0, j = 1 .. N.

© Oxford University Press 2011

 Singhal’s Heuristic token based
algorithm
• Requesting CS
– If Si has no token and requests CS:
• SVi[i] := R. SNi[i] := SNi[i] + 1.
• Send REQUEST(i,sn) to sites Sj for which SVi[j] = R. (sn: sequence
number, updated value of SNi[i]).
– Receiving REQUEST(i,sn): if sn <= SNj[i], ignore. Otherwise, update
SNj[i] and do:
• SVj[j] = N -> SVj[i] := R.
• SVj[j] = R -> If SVj[i] != R, set it to R & send REQUEST(j,SNj[j]) to Si.
Else do nothing.
• SVj[j] = E -> SVj[i] := R.
• SVj[j] = H -> SVj[i] := R, TSV[i] := R, TSN[i] := sn, SVj[j] = N. Send
token to Si.
• Executing CS: after getting token. Set SVi[i] := E.

© Oxford University Press 2011

 Singhal’s Heuristic token based
algorithm
• Releasing CS
– SVi[i] := N, TSV[i] := N. Then, do:
• For other Sj: if (SNi[j] > TSN[j]), then {TSV[j] := SVi[j]; TSN[j] :=
SNi[j]}
• else {SVi[j] := TSV[j]; SNi[j] := TSN[j]}
– If SVi[j] = N, for all j, then set SVi[i] := H. Else send token to a site Sj
provided SVi[j] = R.

© Oxford University Press 2011

 THANK YOU

© Oxford University Press 2011