An Efficient Token Passing Strategy in Improved Logical Ring Structure

Zhonglan      Luo; Kai      Lu; Xiaoping      Wang

Abstract

This paper presents a fault-tolerant mutual exclusion dual-token algorithm named DTME in distributed system. The DTME algorithm is a kind of algorithm which is based on the token ring approach. It uses two tokens which can detect each other but have different function. With a new logical ring structure, the DTME algorithm uses a novel token passing strategy to arbitrate resources shared by multi-process simultaneously. The safety, liveness and robustness properties of the DTME algorithm have been proved in this paper. In addition, we design a corresponding recovery mechanism by analyzing the impact of node failures and loss of tokens. The evaluation shows that we obtained a better result on the fault-tolerant property, average message complexity and average waiting time of the algorithm by means of simulation, compared with Jayadev Misra’s algorithm and Hoda Taheri’s algorithm. Here we also discuss few patents that are relevant to the article.

Keywords: Distributed system, Mutual exclusion, Dual-token ring, Fault-tolerant.Distributed system, Mutual exclusion, Dual-token ring, Fault-tolerant.Distributed system, Mutual exclusion, Dual-token ring, Fault-tolerant.