Notes on the algorithm Suzuki–Kasami algorithm

1 notes on algorithm

1.1 requesting cs
1.2 executing cs
1.3 releasing cs
1.4 performance

notes on algorithm

only site holding token can access cs




all processes involved in assignment of cs




request messages sent nodes




not based on lamport’s logical clock
the algorithm uses sequence numbers instead




used keep track of outdated requests
they advance independently on each site

the main design issues of algorithm:

telling outdated requests current ones
determining site going token next

data structures used deal these 2 aspects:

each site si has array rni[1..n] store sequence
number of latest requests received other sites

the token contains 2 data structures:

the token array ln[1..n] keeps track of request executed on each site
the token queue q queue of requesting sites

requesting cs

if site not have token, increases sequence number rni[i] , sends request(i, sn) message other sites (sn= rni[i])
when site sj receives message, sets rnj[i] max(rnj[i], sn). if sj has idle token, them sends token si if rnj[i] = ln[i]+1

executing cs

site si executes cs when has received token

releasing cs

when done cs, site si sets ln[i] = rni[i]
for every site sj id not in token queue, appends id token queue if rni[j] =ln[j]+1
if queue not empty, extracts id @ head of queue , sends token site

performance

either 0 or n messages cs invocation (no messages if process holds token; otherwise



n
−
1


{\displaystyle n-1}

requests ,



1


{\displaystyle 1}

reply)
synchronization delay 0 or n