An Improved Token-Based and Starvation Free Distributed Mutual Exclusion Algorithm

Subject Areas : Journal of Computer & Robotics

Om-Kolsoom  Shahryari ¹ (Department of Computer Engineering, Sanandaj Branch, Islamic Azad University, Sanandaj, Iran)
Ali  Broumandnia ² (Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran)

Received: 2017-01-31 Accepted : 2018-08-27 Published : 2018-09-01

Keywords: Critical Section, Concurrency, Distributed System, Mutual Exclusion, Message Passing, Token-based Algorithm,

Abstract :

Distributed mutual exclusion is a fundamental problem of distributed systems that coordinates the access to critical shared resources. It concerns with how the various distributed processes access to the shared resources in a mutually exclusive manner. This paper presents fully distributed improved token based mutual exclusion algorithm for distributed system. In this algorithm, a process which has owing token, could enter to its critical section. The processes communicate to each other in an asynchronous message passing manner. We assume the distributed processes are organized in a wraparound two dimensional array. Also, the communication graph of the network is supposed to be a complete graph. The proposed algorithm uses three types of messages, namely ReqMsg, InfoMsg and RelMsg. Beside token-holding node, there are some nodes, we call them informed-nodes, which can know token-holding node and transmit request message to it directly. The number of messages, which are exchanged per each critical section entrance, is a key parameter to avoid posing additional overhead to the distributed system. In this paper, we obtain to messages per critical section access where N is the number of nodes in the system. The proposed algorithm outperforms other token based algorithms whilst fairness is kept and the proposed algorithm is starvation free.