Deadlock-Free Information Structure Distributed Mutual Exclusion Algorithms
Umberto Bonollo
Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.
umberto@cs.mu.oz.au
Elizabeth A. Sonenberg
Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.
eas@cs.mu.oz.au
Abstract
In the distributed mutual exclusion problem, a set of processes must
coordinate their actions so that at any time at most one process may
be within its critical section. Information structure distributed
mutual exclusion algorithms (ISDME) are instances of a general
algorithm which can represent several non-token-based algorithms. This
paper introduces a new deadlock-free ISDME algorithm (DF-ISDME) which
operates on a restricted class of information structures. DF-ISDME
allows deadlock-free solutions for a wider class of information
structure topologies than a previously identified class of
deadlock-free Maekawa algorithms (DF-Maekawa), but retains the same
throughput as DF-Maekawa. The paper provides a detailed description of
the DF-ISDME algorithm, and correctness proofs. Message performance of
the new algorithm is discussed, as are potential application scenarios.
Conference Home Page