Suzuki–Kasami algorithm

The Suzuki-Kasami algorithm is a token-based algorithm for achieving mutual exclusion in distributed systems.

Main points

Some Points about the Suzuki Kasami algorithm are:

• 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

Data structures used to deal with these two aspects:

• Each site Si has an array RNi[1..N] to store the sequence
• Number of the latest requests received from other sites

The token contains two data structures:

• The token array LN[1..N] keeps track of the request executed most recently on each site
• The token queue Q is a queue of requesting sites

Requesting the CS:

• If the site does not have the token, then it increases its sequence number RNi[i] and sends a request(i, sn) message to all other sites (sn= RNi[i])
• When a site Sj receives this message, it sets RNj[i] to max(RNj[i] , sn). If Sj has the idle token, them it sends the token to Si if RNj[i] = LN[i]+1

Executing the CS

• Site Si executes the CS when it has received the token

Releasing the CS

• When done with the CS, site Si sets LN[i] = RNi[i]
• For every site Sj whose ID is not in the token queue, it appends its ID to the token queue if RNi[j] =LN[j]+1
• If the queue is not empty, it extracts the ID at the head of the queue and sends the token to that site

Performance

• 0 or N messages for CS invocation
• Synchronization delay is 0 or N