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 nprocess, kcomponent 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 lockfree 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 nprocess implementation of a scannable object O with k fully reusable components from an arbitrary set of objects with bounded domain sizes. We construct a lockfree 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 obstructionfreedom, we construct an implementation from k objects of the same types as the components of O along with ⌈n/(b1)⌉ 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 + (n1)/b  log_b n) objects are required. This asymptotically matches our obstructionfree upper bound. When n > b^k  bk + k, we prove that 1/2⋅ (b^{k1}  {(b1)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:130:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772556},
ISSN = {18688969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17221},
URN = {urn:nbn:de:0030drops172213},
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 