|
In the problem of mutual exclusion, concurrent access to a
shared resource using a structural program abstraction called a
Critical Section (CS) must be synchronized such that at any
time only one process can enter the CS. In a distributed
system, due to the lack of both in shared memory and a global
clock, and due to unpredictable message delay, the design of a
distributed mutual exclusion protocol that is free from
deadlock and starvation, is much more complex than that in a
centralized system. To reduce the overhead of achieving mutual
exclusion while supporting fault tolerance, in the thesis, we
apply the triangular-mesh-based approach to design fault-
tolerant protocols for mutual exclusion, in which the nodes in
the system are organized into a triangular mesh. We propose
three protocols based on the triangular mesh: the triangular
mesh protocol, the triple triangular mesh protocol and the
dynamic triangular mesh protocol. In the triangular mesh
protocol, we associate with each node two special patterns. The
nodes in each special pattern constitute a quorum. In the
triple triangular mesh protocol, a quorum contains nodes from
some side of each of three subtriangles in the triangular mesh.
In the dynamic triangular mesh protocol, three dynamic paths
constitute a quorum in the given triangular mesh. The quorum
size of these proposed protocols is K that is $O(sqrt(N)),
where N =(K*(K+1))/2 is the number of nodes in the system. In
the worst case, the triangular mesh protocol, the triple
triangular mesh protocol and the dynamic triangular mesh
protocol are fault-tolerant up to K-2, K-2 and K-1 site and
communication failures, respectively. From our simulation
study, these three proposed protocol can have higher
availability than Cheung et al.'s grid protocol. Moreover, the
quorum size of the proposed protocols will be less than that in
Kumar's HQC protocol when N is greater than or equal to 15 and
less than that in Agrawal et al.'s tree quorum protocol when
node
|