Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Space Bounds for Adaptive Renaming
verfasst von : Maryam Helmi, Lisa Higham, Philipp Woelfel
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
We study the space complexity of implementing long-lived and one-shot adaptive renaming from multi-reader multi-writer registers, in an asynchronous distributed system with
n
processes. In an
f
(
k
)
-adaptive renaming algorithm
each participating process gets a distinct name, in the range {1,…,
f
(
k
)} provided
k
processes participate.
We show that any obstruction-free long-lived
f
(
k
)-adaptive renaming object requires
m
registers, where
m
≤
n
− 1 is the largest integer such that
f
(
m
) ≤
n
− 1. This implies a lower bound of
n
−
c
registers for long-lived (
k
+
c
)-adaptive renaming, which is tight. We also prove a lower bound of
$\lfloor \frac{n}{c+1} \rfloor$
registers for implementing any obstruction-free one-shot (
k
+
c
)-adaptive renaming.
We also provide one-shot renaming algorithms, e.g., a wait-free one-shot
$(\frac{3k^2}{2})$
-adaptive one from
$\lceil \sqrt{n} \rceil $
registers, and an obstruction-free one-shot
f
(
k
)-adaptive renaming algorithm from only ⌈
f
− 1
(
n
) ⌉ registers.