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 algorithmRicart, Glenn, and Ashok K. Agrawala.
An optimal algorithm for mutual exclusion in computer networks
" Communications of the ACM 24.1 (1981): 9-17. 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$ be the number of processes. Each process is identified by an integer in $1, ..., n$.

Data structures

Each process maintains one data structure:

* an array RN_i /math> (for Request Number), $i$ being the ID of the process containing this array, where RN_i /math> stores the last Request Number received by $i$ from $j$

The token contains two data structures:

* an array LN /math> (for Last request Number), where LN /math> stores the most recent Request Number of process $j$ for which the token was successfully granted
* a queue $Q$, storing the ID of processes waiting for the token

Algorithm

Requesting the critical section (CS)

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

* increments its sequence number RN_i /math>
* sends a request message containing new sequence number to all processes in the system

Releasing the CS

When process $i$ leaves the CS, it:

* sets LN /math> of the token equal to RN_i /math>. This indicates that its request RN_i /math> has been executed
* for every process $k$ not in the token queue $Q$, it appends $k$ to $Q$ if RN_i = LN + 1. This indicates that process $k$ has an outstanding request
* if the token queue $Q$ is not empty after this update, it pops a process ID $j$ from $Q$ and sends the token to $j$
* otherwise, it keeps the token

Receiving a request

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

* sets RN_j /math> to max(RN_j s) (if s < RN_j /math>, the message is outdated)
* if process $j$ has the token and is not in CS, and if RN_j

LN + 1 (indicating an outstanding request), it sends the token to process $i$

Executing the CS

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

Performance

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

References

{{DEFAULTSORT:Suzuki-Kasami algorithm
Distributed algorithms