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.
