The Weak Mutual Exclusion Problem.

P. Romano, L. Rodrigues and N. Carvalho.

Selected sections of this report will be published in the Proceedings of the International Parallel and Distributed Processing Symposium, Rome, Italy, May 2009.

Abstract

In this paper we define the Weak Mutual Exclusion (WME) problem. Analogously to classical Distributed Mutual Exclusion (DME), WME serializes the accesses to a shared resource. Differently from DME, however, the WME abstraction regulates the access to a replicated shared resource, whose copies are locally maintained by every participating process. Also, in WME, processes suspected to have crashed are possibly ejected from the critical section

We prove that, unlike DME, WME is solvable in a partially synchronous model, i.e. a system where the bounds on communication latency and on relative process speeds are not known in advance, or are known but only hold after an unknown time.

Finally we demonstrate that diamond P is the weakest failure detector for solving WME, and present an algorithm that solves WME using diamond P with a majority of correct processes.

Also available extended report (pdf).


Luís Rodrigues