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 n {\displaystyle n} be the number of processes. Each process is identified by an integer in 1 , . . . , n {\displaystyle 1,...,n}.

Data structures

Each process maintains one data structure:

  • an array R N i [ n ] {\displaystyle RN_{i}[n]} (for Request Number), i {\displaystyle i} being the ID of the process containing this array, where R N i [ j ] {\displaystyle RN_{i}[j]} stores the last Request Number received by i {\displaystyle i} from j {\displaystyle j}

The token contains two data structures:

  • an array L N [ n ] {\displaystyle LN[n]} (for Last request Number), where L N [ j ] {\displaystyle LN[j]} stores the most recent Request Number of process j {\displaystyle j} for which the token was successfully granted
  • a queue Q {\displaystyle Q}, storing the ID of processes waiting for the token

Algorithm

Requesting the critical section (CS)

When process i {\displaystyle i} wants to enter the CS, if it does not have the token, it:

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

Releasing the CS

When process i {\displaystyle i} leaves the CS, it:

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

Receiving a request

When process j {\displaystyle j} receives a request from i {\displaystyle i} with sequence number s {\displaystyle s}, it:

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

Executing the CS

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

Performance

  • Either 0 {\displaystyle 0} or N {\displaystyle N} messages for CS invocation (no messages if process holds the token; otherwise N − 1 {\displaystyle N-1} requests and 1 {\displaystyle 1} reply)
  • Synchronization delay is 0 {\displaystyle 0} or N {\displaystyle N} (N − 1 {\displaystyle N-1} requests and 1 {\displaystyle 1} 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