𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Quorum-Based Self-Stabilizing Distributed Mutual Exclusion Algorithm

✍ Scribed by Mikhail Nesterenko; Masaaki Mizuno

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
187 KB
Volume
62
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we present a self-stabilizing quorum-based distributed mutual exclusion algorithm. Our algorithm is designed for an asynchronous message-passing model. The algorithm scales well since it has constant synchronization delay and its message complexity is proportional to the square root of the number of processes in the system. The algorithm tolerates message loss. The algorithm places few assumptions on timeouts needed for its implementation. All this allows for a ready implementation of the algorithm on practical distributed architectures.

πŸ“œ SIMILAR VOLUMES

A Log (N) Distributed Mutual Exclusion A
A Log (N) Distributed Mutual Exclusion Algorithm Based on Path Reversal
✍ Mohamed Naimi; Michel Trehel; AndrΓ© Arnold πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 378 KB

Several algorithms reducing the number of messages were presented later (see Ricart and Agrawala [21] and Carvalho and Roucairol [4]). The number of messages was proportional to N. The algorithm presented by Chandy and Misra [6] (in which permission is in the form of a fork) is the most efficient of

Uniform and Self-Stabilizing Fair Mutual
Uniform and Self-Stabilizing Fair Mutual Exclusion on Unidirectional Rings under Unfair Distributed Daemon
✍ Hirotsugu Kakugawa; Masafumi Yamashita πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 180 KB

This paper presents a uniform randomized self-stabilizing mutual exclusion algorithm for an anonymous unidirectional ring of any size n, running under an unfair distributed scheduler (d-daemon). The system is stabilized with probability 1 in Oðn 3 Þ expected number of steps, and each process is priv