Fault-Tolerant Token Based Algorithm for Mutual Exclusion in Distributed Environment

Abstract

In distributed computing, many problems require a shared object to be allocated to a number of requesting processing in mutually exclusive manner. Hence the mutual exclusion problem plays a vital role in the design of distributed systems. A considerable amount of literature is available on this problem. The performance metrics of the mutual algorithm are the number of messages required per CS invocation, response time. Moreover, it should be starvation-free and deadlock-free. The algorithms available in literature vary in different ways viz. the performance of the algorithm under low and high load, resilience behavior the algorithm. Most of the tokenbased algorithms take O (n) messages per CS invocation. Some of the algorithms are not resilient to site and communication failure. The algorithm implemented here in this thesis for mutual exclusion in distributed environment is token-based. It takes 2-3 messages per CS invocation at low load and a few more at higher load. This algorithm is starvation-free and deadlock-free, but not resilient to site and communication failure. Using broadcast, this algorithm has been modified to be immune to site and communication failure. To implement this, I have used PARSEC simulator that is a C-based discrete-event simulation language. It adopts the process interaction approach to discrete-event simulation. The simulation results prove that this algorithm is more efficient as compared to algorithms in literature in terms of number of messages passed per CS invocation.