Multi-level Clustering of nodes for distributed mutual exclusion

Abstract

Distributed and Parallel Systems have become attractive as well as important due to its cost effectiveness and better performance. A Distributed system is a collection of computing sites where any node has only partial or incomplete view of the total system. If different processes are running on different nodes having some shared data or resources then it is very important to keep the consistency of any shared resource. Achieving such goal is called Mutual Exclusion (ME). The part of code where the shared resource is accessed is called critical section (CS) or critical region. Mutual Exclusion is achieved by not letting more than one process access the CS. Many problems in distributed system, which involves replicated data, atomic commitment, distributed shared memory etc., require mutual exclusion. Different kinds of distributed algorithms: especially token based and permission based, have been proposed for the solution of the Mutual Exclusion problems. Quorum based algorithms is one kind of permission-based solution and shows better performance in distributed environment. Hybrid solutions are also proposed by incorporating the good features of the existing algorithms. With the emergence of peer-to-peer computing, the distributed applications have spread over a large number of nodes. Cluster-based solutions are scalable for large number of participants. This thesis presents a permission-based solution for multilevel clustered network, where a cluster might be a collection of small clusters. We apply a quorum-based algorithm, tree-quorum algorithm, at different level of clusters. A coordination algorithm is proposed to communicate between the different levels of this structure. Our technique is generalized as any kind of algorithm, centralized or distributed, token based or quorum based, can be applied at any level. We have also proved that coordination algorithm maintains Mutual Exclusion correctly. An analytic expression of optimal level of clustering shows that it depends on the network size and the availability of nodes. Finally a simulation of the clustered network is conducted to demonstrate the performance of the new technique using different classical ME algorithms in different levels of the clustered network.