Suzuki kasami

 


Formal Definition: Suzuki-Kasami’s Broadcast Algorithm

Suzuki-Kasami’s Broadcast Algorithm is a token-based distributed mutual exclusion algorithm that ensures only one site can enter the critical section (CS) at a time in a distributed system. A unique token is shared among all sites, and the site holding the token is granted permission to execute its CS.

When a site requires entry to the CS and does not hold the token, it broadcasts a REQUEST message with its sequence number to all other sites. Each site maintains:

  1. RN[1…N] – An array recording the largest sequence number received from each site.
  2. LN[1…N] – An array inside the token recording the most recent request executed for each site.
  3. Q – A queue of sites with outstanding requests.
  • A REQUEST message is considered outdated if its sequence number is less than or equal to the value already stored in RN.
  • A site has an outstanding request if RN[j] = LN[j] + 1.

Algorithm Steps:

  1. Requesting CS: A site increments its sequence number and broadcasts a REQUEST(i, sn). If another site has the token and the request is valid, it forwards the token.
  2. Executing CS: A site executes its CS only after receiving the token.
  3. Releasing CS: After CS execution, the site updates LN[i] = RN[i], checks for pending requests, updates Q, and passes the token to the next site in Q.


Properties:

  • Mutual Exclusion: Guaranteed since only one token exists in the system.
  • Fairness: Requests are satisfied in increasing sequence number order.
  • Liveness: Every valid request is eventually granted in finite time.

Performance:

  • Requires 0 or N broadcast messages per CS entry.
  • Synchronization delay = 0 if the site already holds the token.
  • Message complexity is efficient compared to non-token-based algorithms.


9.11 Suzuki-Kasami's Broadcast Algorithm

In Suzuki-Kasami's algorithm (Algorithm 9.7), when a site wants to enter the critical section (CS) and does not have the token, it broadcasts a REQUEST message to all sites. The site with the token sends it to the requester. If a site is already executing the CS, it sends the token only after completing its execution.

Major Design Issues

  1. Outdated REQUEST message vs Current REQUEST message:
    Due to message delays, a site may receive an old REQUEST after the request is already satisfied. This may waste messages and cause delays. So, sites must distinguish outdated messages.

  2. Determining outstanding requests:
    After finishing the CS, a site must know which sites have pending requests. The challenge is updating all sites efficiently about satisfied requests.

Handling Outdated REQUEST Messages

  • A REQUEST has the form REQUEST(j, n) where n is the sequence number of site Sj.
  • Each site maintains an array RN[1…N].
  • RN[j] stores the largest sequence number seen from Sj.
  • If a site receives REQUEST(j, n), it updates RN[j] = max(RN[j], n).
  • A request is outdated if RN[j] > n.

Handling Outstanding Requests

  • The token contains:
    • Q: queue of requesting sites.
    • LN[1…N]: array storing the last executed request number of each site.
  • After CS execution, site Si updates LN[i] = RN[i].
  • A site Sj is requesting the CS if RN[j] = LN[j] + 1.
  • Such sites are added to queue Q.
  • The token is sent to the site at the head of Q.

Algorithm 9.7 – Suzuki-Kasami’s Broadcast Algorithm

Requesting the Critical Section:

  1. If site Si does not have the token, it increments RN[i] and sends REQUEST(i, sn) to all sites.
  2. On receiving this, site Sj updates RN[i] = max(RN[i], sn). If Sj has the idle token and RN[i] = LN[i] + 1, it sends the token to Si.

Executing the Critical Section:
3. Site Si executes CS after receiving the token.

Releasing the Critical Section:
4. Si updates LN[i] = RN[i].
5. For each site Sj, if RN[j] = LN[j] + 1 and Sj is not in Q, add Sj to Q.
6. If Q is non-empty, send token to the site at the head of Q.

Correctness

  • Mutual exclusion is guaranteed since only one token exists.
  • Theorem 9.3: A requesting site enters CS in finite time because requests reach all sites in finite time, and the token queue ensures fairness.

Performance

  • The algorithm is simple and efficient.
  • Requires 0 or N messages per CS invocation.
  • Synchronization delay = 0 if the site already has the token.