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.

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

Each process maintains one data structure:

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

The token contains two data structures:

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

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

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

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

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

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

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

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

• Either ${\displaystyle 0}${\displaystyle 0} or ${\displaystyle N}${\displaystyle N} messages for CS invocation (no messages if process holds the token; otherwise ${\displaystyle N-1}${\displaystyle N-1} requests and ${\displaystyle 1}${\displaystyle 1} reply)
• Synchronization delay is ${\displaystyle 0}${\displaystyle 0} or ${\displaystyle N}${\displaystyle N} (${\displaystyle N-1}${\displaystyle N-1} requests and ${\displaystyle 1}${\displaystyle 1} reply)

• 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

• Distributed algorithms

• Articles needing additional references from September 2014
• All articles needing additional references