License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.30
URN: urn:nbn:de:0030-drops-172213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17221/
Ovens, Sean
The Space Complexity of Scannable Objects with Bounded Components
Abstract
A fundamental task in the asynchronous shared memory model is obtaining a consistent view of a collection of shared objects while they are being modified concurrently by other processes. A scannable object addresses this problem. A scannable object is a sequence of readable objects called components, each of which can be accessed independently. It also supports the Scan operation, which simultaneously reads all of the components of the object. In this paper, we consider the space complexity of an n-process, k-component scannable object implementation from objects with bounded domain sizes. If the value of each component can change only a finite number of times, then there is a simple lock-free implementation from k objects. However, more objects are needed if each component is fully reusable, i.e. for every pair of values v, v', there is a sequence of operations that changes the value of the component from v to v'.
We considered the special case of scannable binary objects, where each component has domain {0, 1}, in PODC 2021. Here, we present upper and lower bounds on the space complexity of any n-process implementation of a scannable object O with k fully reusable components from an arbitrary set of objects with bounded domain sizes. We construct a lock-free implementation from k objects of the same types as the components of O along with ⌈n/b⌉ objects with domain size 2^b. By weakening the progress condition to obstruction-freedom, we construct an implementation from k objects of the same types as the components of O along with ⌈n/(b-1)⌉ objects with domain size b.
When the domain size of each component and each object used to implement O is equal to b and n ≤ b^k - bk + k, we prove that 1/2⋅ (k + (n-1)/b - log_b n) objects are required. This asymptotically matches our obstruction-free upper bound. When n > b^k - bk + k, we prove that 1/2⋅ (b^{k-1} - {(b-1)k + 1}/b) objects are required. We also present a lower bound on the number of objects needed when the domain sizes of the components and the objects used by the implementation are arbitrary and finite.
BibTeX - Entry
@InProceedings{ovens:LIPIcs.DISC.2022.30,
author = {Ovens, Sean},
title = {{The Space Complexity of Scannable Objects with Bounded Components}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {30:1--30:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-255-6},
ISSN = {1868-8969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17221},
URN = {urn:nbn:de:0030-drops-172213},
doi = {10.4230/LIPIcs.DISC.2022.30},
annote = {Keywords: space complexity, lower bound, shared memory, snapshot object}
}
|
Keywords: |
|
space complexity, lower bound, shared memory, snapshot object |
|
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
17.10.2022 |
