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

Data structures

Each process maintains one data structure:

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

The token contains two data structures:

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

Algorithm

Requesting the critical section (CS)

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

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

Releasing the CS

When process [math]\displaystyle{ i }[/math] leaves the CS, it:

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

Receiving a request

When process [math]\displaystyle{ j }[/math] receives a request from [math]\displaystyle{ i }[/math] with sequence number [math]\displaystyle{ s }[/math], it:

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

Executing the CS

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

Performance

• Either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ N }[/math] messages for CS invocation (no messages if process holds the token; otherwise [math]\displaystyle{ N-1 }[/math] requests and [math]\displaystyle{ 1 }[/math] reply)
• Synchronization delay is [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ N }[/math] ([math]\displaystyle{ N - 1 }[/math] requests and [math]\displaystyle{ 1 }[/math] 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