In this tutorial you are going to learn about Difference between Token based and Non-Token based Algorithms in Distributed System.
In mutual exclusion algorithm, a site communicates with a set of other sites to arbitrate who should execute the critical section next.
There are two classes of the mutual exclusion algorithms in distributed systems. They are:
- Token based algorithm
- Non-token based algorithm
Token Based Algorithm
- In the Token Based algorithm, a unique token is shared among all the sites. If sites process the token then it is allowed to enter its critical section (CS).
- Token Based Algorithm use sequence numbers instead of timestamps.
- A correction proof of token-based algorithm is to ensure that the mutual exclusion enforced is trivial. An algorithm guarantees mutual exclusion as long as a site holds the token during the execution of the critical section.
The algorithms that comes under the Token based algorithm are
- Suzuki-kasami’s broadcast algorithm
- Singhal’s heuristic algorithms
- Raymond’s tree based algorithms
Example: If p1, p2 and p3 requests to enter the critical section at the same time to execute it, the process that has tokens will only be given permission to execute the critical section.
Non-Token Based Algorithm
- In the Non-token algorithm, it uses timestamps to order the requests for the critical section and to resolve conflicts between simultaneous requests.
- In the Non-Token based mutual exclusion algorithm, a site communicates with a set of other sites to determine who should execute the critical section next.
- Mutual exclusion is enforced because the assertion becomes true only at the given time.
Algorithms that come under Non-token based algorithms are
- Lamport algorithm
- Ricart-Agrawal’s algorithm
- Maekawa’s algorithm.
- Each request for the critical section gets a timestamp and small timestamps requests have a priority over larger timestamps requests. Each process freely and equally competes for the right to use the shared resources; requests are arbitrated by the central control sites or by the distributed agreement.
Example: If process p1 has timestamp 2 and p2 has timestamp 3, requests to execute the critical section at the same time. P1 will be given the priority to execute the critical section and p2 will not be given the permission to execute the critical section.
Difference between the token based algorithm and Non-token based algorithm
| Token Based Algorithm | Non-Token Based Algorithm |
| Uses token to enter into Critical section | No token is required to enter into critical section |
| Uses sequence number to execute the critical section | Uses timestamps to enter the critical section |
| Every request has a sequence number to enter the critical section | Every request has a timestamp to enter the critical section |
| Higher sequence number will be having the lowest priority | Higher the timestamp, lower the priority |
| Example: Suzuki-kasami’s broadcast algorithm | Example: Ricart-agrawal’s algorithm |
This article on Difference between Token based and Non-Token based Algorithms in Distributed System is contributed by Hemalatha P. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com