Suzuki–Kasami algorithm

Each process maintains one data structure:

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

The token contains two data structures:

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

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

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

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

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

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

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

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

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