Suzuki–Kasami algorithm

Suzuki kasami algorithm is a Token based algorithm for achieving mutual exclusion in Distributed System.

Some Points about Suzuki Kasami are--

– only the site currently holding the token can access the CS • All processes involved in the assignement 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

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