Suzuki–Kasami algorithm

<h2 id="algorithm-description">Algorithm description</h2>
<p>Let 
  
    
      
        n
      
    
    {\displaystyle n}
  
 be the number of processes. Each process is identified by an integer in 
  
    
      
        1
        ,
        .
        .
        .
        ,
        n
      
    
    {\displaystyle 1,...,n}
  
.
</p>
<h3>Data structures</h3>
<p>Each process maintains one data structure:
</p>
<ul><li>an array 
  
    
      
        R
        
          N
          
            i
          
        
        [
        n
        ]
      
    
    {\displaystyle RN_{i}[n]}
  
 (for Request Number), 
  
    
      
        i
      
    
    {\displaystyle i}
  
 being the ID of the process containing this array, where 
  
    
      
        R
        
          N
          
            i
          
        
        [
        j
        ]
      
    
    {\displaystyle RN_{i}[j]}
  
 stores the last Request Number received by 
  
    
      
        i
      
    
    {\displaystyle i}
  
 from 
  
    
      
        j
      
    
    {\displaystyle j}
  
</li></ul>
<p>The token contains two data structures:
</p>
<ul><li>an array 
  
    
      
        L
        N
        [
        n
        ]
      
    
    {\displaystyle LN[n]}
  
 (for Last request Number), where 
  
    
      
        L
        N
        [
        j
        ]
      
    
    {\displaystyle LN[j]}
  
 stores the most recent Request Number of process 
  
    
      
        j
      
    
    {\displaystyle j}
  
 for which the token was successfully granted</li>
<li>a queue 
  
    
      
        Q
      
    
    {\displaystyle Q}
  
, storing the ID of processes waiting for the token</li></ul>
<h3>Algorithm</h3>
<h4>Requesting the critical section (CS)</h4>
<p>When process 
  
    
      
        i
      
    
    {\displaystyle i}
  
 wants to enter the CS, if it does not have the token, it:
</p>
<ul><li>increments its sequence number 
  
    
      
        R
        
          N
          
            i
          
        
        [
        i
        ]
      
    
    {\displaystyle RN_{i}[i]}
  
</li>
<li>sends a request message containing new sequence number to all processes in the system</li></ul>
<h4>Releasing the CS</h4>
<p>When process 
  
    
      
        i
      
    
    {\displaystyle i}
  
 leaves the CS, it:
</p>
<ul><li>sets 
  
    
      
        L
        N
        [
        i
        ]
      
    
    {\displaystyle LN[i]}
  
 of the token equal to 
  
    
      
        R
        
          N
          
            i
          
        
        [
        i
        ]
      
    
    {\displaystyle RN_{i}[i]}
  
. This indicates that its request 
  
    
      
        R
        
          N
          
            i
          
        
        [
        i
        ]
      
    
    {\displaystyle RN_{i}[i]}
  
 has been executed</li>
<li>for every process 
  
    
      
        k
      
    
    {\displaystyle k}
  
 not in the token queue 
  
    
      
        Q
      
    
    {\displaystyle Q}
  
, it appends 
  
    
      
        k
      
    
    {\displaystyle k}
  
 to 
  
    
      
        Q
      
    
    {\displaystyle Q}
  
 if 
  
    
      
        R
        
          N
          
            i
          
        
        [
        k
        ]
        =
        L
        N
        [
        k
        ]
        +
        1
      
    
    {\displaystyle RN_{i}[k]=LN[k]+1}
  
. This indicates that process 
  
    
      
        k
      
    
    {\displaystyle k}
  
 has an outstanding request</li>
<li>if the token queue 
  
    
      
        Q
      
    
    {\displaystyle Q}
  
 is not empty after this update, it pops a process ID 
  
    
      
        j
      
    
    {\displaystyle j}
  
 from 
  
    
      
        Q
      
    
    {\displaystyle Q}
  
 and sends the token to 
  
    
      
        j
      
    
    {\displaystyle j}
  
</li>
<li>otherwise, it keeps the token</li></ul>
<h4>Receiving a request</h4>
<p>When process 
  
    
      
        j
      
    
    {\displaystyle j}
  
 receives a request from 
  
    
      
        i
      
    
    {\displaystyle i}
  
 with sequence number 
  
    
      
        s
      
    
    {\displaystyle s}
  
, it:
</p>
<ul><li>sets 
  
    
      
        R
        
          N
          
            j
          
        
        [
        i
        ]
      
    
    {\displaystyle RN_{j}[i]}
  
 to 
  
    
      
        m
        a
        x
        (
        R
        
          N
          
            j
          
        
        [
        i
        ]
        ,
        s
        )
      
    
    {\displaystyle max(RN_{j}[i],s)}
  
 (if 
  
    
      
        s
        <
        R
        
          N
          
            j
          
        
        [
        i
        ]
      
    
    {\displaystyle s<RN_{j}[i]}
  
, the message is outdated)</li>
<li>if process 
  
    
      
        j
      
    
    {\displaystyle j}
  
 has the token and is not in CS, and if 
  
    
      
        R
        
          N
          
            j
          
        
        [
        i
        ]
        ==
        L
        N
        [
        i
        ]
        +
        1
      
    
    {\displaystyle RN_{j}[i]==LN[i]+1}
  
 (indicating an outstanding request), it sends the token to process 
  
    
      
        i
      
    
    {\displaystyle i}
  
</li></ul>
<h4>Executing the CS</h4>
<p>A process enters the CS when it has acquired the token.
</p>
<h3>Performance</h3>
<ul><li>Either 
  
    
      
        0
      
    
    {\displaystyle 0}
  
 or 
  
    
      
        N
      
    
    {\displaystyle N}
  
 messages for CS invocation (no messages if process holds the token; otherwise 
  
    
      
        N
        −
        1
      
    
    {\displaystyle N-1}
  
 requests and 
  
    
      
        1
      
    
    {\displaystyle 1}
  
 reply)</li>
<li>Synchronization delay is 
  
    
      
        0
      
    
    {\displaystyle 0}
  
 or 
  
    
      
        N
      
    
    {\displaystyle N}
  
 (
  
    
      
        N
        −
        1
      
    
    {\displaystyle N-1}
  
 requests and 
  
    
      
        1
      
    
    {\displaystyle 1}
  
 reply)</li></ul>
<h2 id="notes-on-the-algorithm">Notes on the algorithm</h2>
<ul><li>Only the site currently holding the token can access the CS</li></ul>
<ul><li>All processes involved in the assignment of the CS</li></ul>
<ul><li>Request messages sent to all <a href="/facts/Node_(networking)/LBp2vNcJ">nodes</a></li></ul>
<ul><li>Not based on <a href="/facts/Lamport_timestamps/Dpxw6Ia4">Lamport’s logical clock</a></li>
<li>The algorithm uses sequence numbers instead</li></ul>
<ul><li>Used to keep track of outdated requests</li>
<li>They advance independently on each site</li></ul>
<p>The main design issues of the algorithm:
</p>
<ul><li>Telling outdated requests from current ones</li>
<li>Determining which site is going to get the token next</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Ichiro Suzuki, Tadao Kasami, [1], ACM Transactions on Computer Systems, Volume 3 Issue 4, Nov. 1985 (pages 344 - 349) <a href="https://dl.acm.org/doi/pdf/10.1145/6110.214406" target="_blank">https://dl.acm.org/doi/pdf/10.1145/6110.214406</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Ricart, Glenn, and Ashok K. Agrawala. "An optimal algorithm for mutual exclusion in computer networks." Communications of the ACM 24.1 (1981): 9-17. <a href="https://apps.dtic.mil/sti/pdfs/ADA083268.pdf" target="_blank">https://apps.dtic.mil/sti/pdfs/ADA083268.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Suzuki–Kasami algorithm open-in-new

Suzuki–Kasami algorithm