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

This is a modification to Ricart–Agrawala algorithm in which a REQUEST and REPLY message are used for attaining the critical section, but in this algorithm, a method was introduced 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  be the number of processes. Each process is identified by an integer in .

Data structures 

Each process maintains one data structure:

 an array  (for Request Number),  being the ID of the process containing this array, where  stores the last Request Number received by  from 

The token contains two data structures:

 an array  (for Last request Number), where  stores the most recent Request Number of process  for which the token was successfully granted
 a queue , storing the ID of processes waiting for the token

Algorithm

Requesting the critical section (CS) 

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

 increments its sequence number 
 sends a request message containing new sequence number to all processes in the system

Releasing the CS 

When process  leaves the CS, it:

 sets  of the token equal to . This indicates that its request  has been executed
 for every process  not in the token queue , it appends  to  if . This indicates that process  has an outstanding request
 if the token queue  is not empty after this update, it pops a process ID  from  and sends the token to 
 otherwise, it keeps the token

Receiving a request 

When process  receives a request from  with sequence number , it:

 sets  to  (if , the message is outdated)
 if process  has the token and is not in CS, and if  (indicating an outstanding request), it sends the token to process

Executing the CS 

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

Performance 
 Either  or  messages for CS invocation (no messages if process holds the token; otherwise  requests and  reply)
 Synchronization delay is  or  ( requests and  reply)

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

References

Distributed algorithms