Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Tight Space Bounds for ℓ-Exclusion
verfasst von : Gadi Taubenfeld
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The simplest deadlock-free algorithm for mutual exclusion requires only one single-writer non-atomic bit per process [4,6,13]. This algorithm is known to be space optimal [5,6]. For over 20 years now it has remained an intriguing open problem whether a similar type of algorithm, which uses only one single-writer bit per process, exists also for ℓ-exclusion for some ℓ ≥ 2.
We resolve this longstanding open problem. For any ℓ and
n
, we provide a tight space bound on the number of single-writer bits required to solve ℓ-exclusion for
n
processes. It follows from our results that it is not possible to solve ℓ-exclusion with one single-writer bit per process, for any ℓ ≥ 2.
In an attempt to understand the inherent difference between the space complexity of mutual exclusion and that of ℓ-exclusion for ℓ ≥ 2, we define a weaker version of ℓ-exclusion in which the liveness property is relaxed, and show that, similarly to mutual exclusion, this weaker version can be solve using one single-writer non-atomic bit per process.