What is the number of messages required per critical-section invocation in the…
2021
What is the number of messages required per critical-section invocation in the Suzuki–Kasami algorithm?
Answer: D. 0 or N — ConceptA token-based mutual-exclusion algorithm counts every network transmission used to grant one critical-section invocation. A broadcast by one of N…
- A.
2(N−1)
- B.
3(N−1)
- C.
0 or (N−1)
- D.
0 or N
Attempted by 355 students.
Show answer & explanation
Correct answer: D
Concept
A token-based mutual-exclusion algorithm counts every network transmission used to grant one critical-section invocation. A broadcast by one of N processes to all other processes contributes N−1 messages, and a direct transfer of the token contributes one message.
Application
If the requesting process already holds the token, it can enter the critical section without sending a REQUEST or transferring the token, so the message count is 0.
If it does not hold the token, it broadcasts a REQUEST to the other N−1 processes.
The process holding the token then sends one PRIVILEGE message carrying the token to the requester.
Thus the nonzero case uses (N−1)+1=N messages.
Cross-check
The original Suzuki–Kasami algorithm states the same two cases: at most N message exchanges for an invocation, or no message when the process with the privilege is the only requester.
Result
Therefore, the message requirement is 0 or N.