Abstract
In this paper, we present a decentralized token generation scheme for token based mutual exclusion algorithms. In this scheme, when a site does not receive the token to access the critical section within a timeout period, it sends a message to every site to generate a new token. When site i receives the message to generate a new token from site j, it generates a new token and sends it to the site to which i had sent the token most recently only if site i had executed the critical section later than site j. On receiving the token from site l, a site retains the token only if it had not executed the critical section since site l had executed the critical section the last time. Unlike other token generation schemes, this scheme is distributed in nature and is more fault-tolerant and efficient. We also present a fault-tolerant token-based mutual exclusion algorithm using this scheme. The complexity of the algorithm is examined in terms of the number of messages exchanged and the delay in generating a new token in the event of token loss.
Original language | English |
---|---|
Pages (from-to) | 45-54 |
Number of pages | 10 |
Journal | Computer Systems Science and Engineering |
Volume | 11 |
Issue number | 1 |
State | Published - Jan 1996 |
Keywords
- Distributed mutual exclusion
- Fault-tolerance
- Token-generation
ASJC Scopus subject areas
- Control and Systems Engineering
- Theoretical Computer Science
- General Computer Science