Suzuki–Kasami algorithm

The Suzuki-Kasami algorithm is a token-based algorithm for achieving mutual exclusion in distributed systems. The process holding the token is the only process able to enter its critical section.

If a process wants to enter its critical section and it does not have the token, it broadcasts a request message to all other processes in the system. The process that has the token, if it is not currently in a critical section, will then send the token to the requesting process. The algorithm makes use of increasing Request Numbers to allow messages to arrive out-of-order.

Algorithm description

Let $n$ be the number of processes. Each process is identified by an integer in $1,...,n$.

Data structures

Each process $i$ maintains three data structures:

• an array $RN[n]$ (for Request Number), where $RN[j]$ stores the last Request Number received from $j$
• an array $LN[n]$ (for Last request Number), where $LN[j]$ stores the most recent Request Number of process $j$ for which the token was successfully sent
• a queue Q, storing the ID of processes waiting for the token

Algorithm

Request vector at process i : RNi[k]contains the largest sequence number received from process k in a requ est message. Token consists of vector and a queue:

LN[k] contains the sequence number of the latest executed

request from process k

Q is the queue of requesting process

Requesting the critical section (CS):

When a process i wants to enter the CS, if it does not have the

token, it:

Increments its sequence number RNi [i]
Sends a request message containing new sequence number to

all processes in the system

When a process k receives the request(i,sn) message, it:
Sets RNk [i] to MAX(RNk [i], sn)

• If sn < RNk [i], the message is outdated

If process k has the token and is not in CS (i.e., is not using token),

and if RNk [i] == LN[i]+1 (indicating an outstanding request) it sends the token to process i

Executing the CS:
A process enters the CS when it has acquired the token.

Suzuki and Kasami’s broadcast algorithm (cont.)

Releasing the CS:

When a process i leaves the CS, it:
Sets LN[i] of the token equal to RNi [i]

• Indicates that its request RNi [i] has been executed

For every process k whose ID is not in the token queue Q, it

appends its ID to Q if RNi [k] == LN[k]+1 • Indicates that process k has an outstanding request F If the token queue Q is nonempty after this update, it deletes the process ID at the head of Q and sends the token to that process • Gives priority to others’ requests • Otherwise, it keeps the token

Evaluation:
0 to N messages required to enter CS

No messages if process holds the token

Otherwise N–1 requests, 1 reply

Main points

Some Points about the Suzuki Kazami algorithm are:

• Only the site currently holding the token can access the CS

• All processes involved in the assignment of the CS

• Request messages sent to all nodes

• Not based on Lamport’s logical clock
• The algorithm uses sequence numbers instead

• Used to keep track of outdated requests
• They advance independently on each site

The main design issues of the algorithm:

• Telling outdated requests from current ones
• Determining which site is going to get the token next

Data structures used to deal with these two aspects:

• Each site Si has an array RNi[1..N] to store the sequence
• Number of the latest requests received from other sites

The token contains two data structures:

• The token array LN[1..N] keeps track of the request executed most recently on each site
• The token queue Q is a queue of requesting sites

Requesting the CS:

• If the site does not have the token, then it increases its sequence number RNi[i] and sends a request(i, sn) message to all other sites (sn= RNi[i])
• When a site Sj receives this message, it sets RNj[i] to max(RNj[i], sn). If Sj has the idle token, them it sends the token to Si if RNj[i] = LN[i]+1

Executing the CS

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

Releasing the CS

• When done with the CS, site Si sets LN[i] = RNi[i]
• For every site Sj whose ID is not in the token queue, it appends its ID to the token queue if RNi[j] =LN[j]+1
• If the queue is not empty, it extracts the ID at the head of the queue and sends the token to that site

Performance

• 0 or N messages for CS invocation
• Synchronization delay is 0 or N