License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.2
URN: urn:nbn:de:0030-drops-130801
Go to the corresponding LIPIcs Volume Portal

Rinberg, Arik ; Keidar, Idit

Intermediate Value Linearizability: A Quantitative Correctness Criterion

LIPIcs-DISC-2020-2.pdf (0.6 MB)


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 wait-free linearizable batched counter from single-writer objects, and propose a wait-free IVL implementation of the same object with an O(1) step complexity for update.

BibTeX - Entry

  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:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-130801},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI