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, 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

edit

Let   be the number of processes. Each process is identified by an integer in  .

Data structures

edit

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

edit

Requesting the critical section (CS)

edit

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

edit

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

edit

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

edit

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

Performance

edit
  • 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

edit
  • 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
  • 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

edit
  1. ^ Ichiro Suzuki, Tadao Kasami, [1], 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.