DECENTRALIZED TOKEN GENERATION SCHEME FOR TOKEN-BASED MUTUAL EXCLUSION ALGORITHMS

In this paper, we present a decentralized token generation scheme for token based mutual exclusion algorithms. In this scheme, when a site d oes not receive the token to access the critical section within a time out 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 secti on later than site j. On receiving the token from site l, a site retai ns the token only if it had not executed the critical section since si te l hav executed the critical section the last time. Unlike other tok en generation schemes, this scheme is distributed in nature and is mor e 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 exchange d and the delay in generating a new token in the event of token loss.