Suzuki–Kasami algorithm (original) (raw)

From Wikipedia, the free encyclopedia

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

Each process maintains one data structure:

The token contains two data structures:

Requesting the critical section (CS)

[edit]

When process i {\displaystyle i} $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]} $RN_{i}[i]$
sends a request message containing new sequence number to all processes in the system

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

Receiving a request

[edit]

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

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

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

^ Ichiro Suzuki, Tadao Kasami, [1], ACM Transactions on Computer Systems, Volume 3 Issue 4, Nov. 1985 (pages 344 - 349)
^ Ricart, Glenn, and Ashok K. Agrawala. "An optimal algorithm for mutual exclusion in computer networks." Communications of the ACM 24.1 (1981): 9-17.