Abstract
Big data processing systems often employ batched updates and data sketches to estimate certain properties of large data. For example, a CountMin sketch approximates the frequencies at which elements occur in a data stream, and a batched counter counts events in batches. This paper focuses on correctness criteria for concurrent implementations of such objects. Specifically, we consider quantitative objects, whose return values are from a totally ordered domain, with a particular emphasis on (ε,δ)bounded objects that estimate a numerical quantity with an error of at most ε with probability at least 1  δ.
The de facto correctness criterion for concurrent objects is linearizability. Intuitively, under linearizability, when a read overlaps an update, it must return the object’s value either before the update or after it. Consider, for example, a single batched increment operation that counts three new events, bumping a batched counter’s value from 7 to 10. In a linearizable implementation of the counter, a read overlapping this update must return either 7 or 10. We observe, however, that in typical use cases, any intermediate value between 7 and 10 would also be acceptable. To capture this additional degree of freedom, we propose Intermediate Value Linearizability (IVL), a new correctness criterion that relaxes linearizability to allow returning intermediate values, for instance 8 in the example above. Roughly speaking, IVL allows reads to return any value that is bounded between two return values that are legal under linearizability. A key feature of IVL is that we can prove that concurrent IVL implementations of (ε,δ)bounded objects are themselves (ε,δ)bounded. To illustrate the power of this result, we give a straightforward and efficient concurrent implementation of an (ε, δ)bounded CountMin sketch, which is IVL (albeit not linearizable).
Finally, we show that IVL allows for inherently cheaper implementations than linearizable ones. In particular, we show a lower bound of Ω(n) on the step complexity of the update operation of any waitfree linearizable batched counter from singlewriter objects, and propose a waitfree IVL implementation of the same object with an O(1) step complexity for update.
BibTeX  Entry
@InProceedings{rinberg_et_al:LIPIcs:2020:13080,
author = {Arik Rinberg and Idit Keidar},
title = {{Intermediate Value Linearizability: A Quantitative Correctness Criterion}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {2:12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771689},
ISSN = {18688969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13080},
URN = {urn:nbn:de:0030drops130801},
doi = {10.4230/LIPIcs.DISC.2020.2},
annote = {Keywords: concurrency, concurrent objects, linearizability}
}
Keywords: 

concurrency, concurrent objects, linearizability 
Collection: 

34th International Symposium on Distributed Computing (DISC 2020) 
Issue Date: 

2020 
Date of publication: 

07.10.2020 