18-04-2012, 11:35 AM
A Timer-free Fault Tolerant K-Mutual Exclusion Algorithm
self-contained.pdf (Size: 446.04 KB / Downloads: 32)
Introduction
Distributed mutual exclusion problem involves processes which communicate
via message passing and need to access a shared resource by executing a segment
of code called the critical section (CS). The problem requires that only
one process be in the critical section at any given time. The k-mutual exclusion
problem is a generalization of the mutual exclusion one by considering k units
of the shared resource. It then allows at most k processes to access these units
simultaneously, i.e., one process per unit. Therefore, a k-mutual exclusion algorithm
must guarantee that at most k processes can be in its critical section at
any time (safety property) and that every request for critical section execution
is eventually satised (liveness property).
Computation model
We consider a distributed system consisting of a nite set of nodes named
= {p1, . . . , p||}, where || > 1. The set of participants is known by all
nodes. There is one process per node. Hence, the words node and process are
interchangeable. Every pair of nodes is assumed to be connected by means of
a reliable communication channel and processes communicate by sending and
receiving messages.
To simplify the presentation, we take the range T of the clock's tick to be
the set of natural numbers. Processes do not have access to T : it is introduced
for the convenience of the presentation.
Description of the Algorithm
Algorithm 1 shows the pseudo-code of our fault tolerant k-mutual exclusion
algorithm. We consider that each process innitely calls the functions Re-
quest_resource() to ask access to a unit of the shared resource, i.e., to execute
the critical section (CS), and calls the Release_resource() when it releases the
CS. Lamport's logical clocks [Lam78] is used for controling causality of events.
Conclusion
Based on Raymond's algorithm, this paper has presented a f-fault tolerant
k-mutual exclusion algorithm where 1 f < k, provided that the underlying
system satises the Responsiveness Property. We have proposed a new approach
for detecting and tolerating failures which is integrated in the k-mutex algorithm
itself and thus renders the solution not expensive.
Furthermore, even if the performance can temporarily degrade just after a
crash, the eciency of the algorithm is dynamically restored as soon as the
remaining processes detect the failure, which does not happen with the original
Raymond's algorithm. Performance experiments on a simulated Grid platform
that satises the RP have shown the eciency and benets of our approach in
comparison to the former.