The Suzuki-Kasami algorithm is a token

Token

A token is an object of value, and may refer to:* In logic, computational linguistics, and information retrieval, a token is an instance of a type; see Type-token distinction...

-based algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 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
  Hypertext Transfer Protocol
  The Hypertext Transfer Protocol is a networking protocol for distributed, collaborative, hypermedia information systems. HTTP is the foundation of data communication for the World Wide Web....
  
   messages sent to all nodes
  Node (networking)
  In communication networks, a node is a connection point, either a redistribution point or a communication endpoint . The definition of a node depends on the network and protocol layer referred to...
  
  
• Not based on Lamport’s logical clock
  Lamport timestamps
  The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and...
  
  
• 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