Suzuki-Kasami algorithm

The Suzuki-Kasami algorithm^[1] 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.

This is a modification to Ricart–Agrawala algorithm^[2] in which a REQUEST and REPLY message are used for attaining the critical section. but in this algorithm they introduced a method in which a seniority vise and also by handing over the critical section to other node by sending a single PRIVILEGE message to other node. So, the node which has the privilege it can use the critical section and if it does not have one it cannot. 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 maintains one data structure:

• an array ${\displaystyle RN[n]}$ (for Request Number), where $RN_{i}[j]$ stores the last Request Number received from $j$

The token contains two data structures:

• 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 granted
• a queue Q, storing the ID of processes waiting for the token

Algorithm

Requesting the critical section (CS)

When process $i$ wants to enter the CS, if it does not have the token, it:

• increments its sequence number $RN_{i}[i]$
• sends a request message containing new sequence number to all processes in the system

Releasing the CS

When process $i$ leaves the CS, it:

• sets $LN[i]$ of the token equal to $RN_{i}[i]$. This indicates that its request $RN_{i}[i]$ has been executed
• for every process $k$ not in the token queue $Q$, it appends $k$ to $Q$ if $RN_{i}[k]=LN[k]+1$. This indicates that process $k$ has an outstanding request
• if the token queue $Q$ is nonempty after this update, it pops a process ID $j$ from $Q$ and sends the token to $j$
• otherwise, it keeps the token

Receiving a request

When process $i$ receives a request from $j$ with sequence number $s$, it:

• sets $RN_{i}[j]$ to $max(RN_{i}[j],s)$ (if $s<RN_{i}[j]$, the message is outdated)
• if process $i$ has the token and is not in CS, and if $RN_{i}[j]==LN[j]+1$ (indicating an outstanding request), it sends the token to process $j$

Executing the CS

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

Notes on the algorithm

• 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

• either 0 or n messages for CS invocation (no messages if process holds the token; otherwise $N-1$ requests and $1$ reply)
• Synchronization delay is 0 or N

References

1. Ichiro Suzuki, Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems, Volume 3 Issue 4, Nov. 1985 (pages 344 - 349)
2. Ricart, Glenn, and Ashok K. Agrawala. "An optimal algorithm for mutual exclusion in computer networks." Communications of the ACM 24.1 (1981): 9-17.