Upper and Lower Bounds for Deterministic Approximate Objects

Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-04
Main Authors: Hendler, Danny, Adnane Khattabi, Milani, Alessia, Travers, Corentin
Format: Article
Language:English
Subjects:
Complexity
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the \(k\)-multiplicative-accurate max register and the \(k\)-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of \(k\) (for some \(k \in \mathbb{N}\)). More accurately, reads are allowed to return an approximate value \(x\) of the maximum value \(v\) previously written to the max register, or of the number \(v\) of increments previously applied to the counter, respectively, such that \(v/k \leq x \leq v \cdot k\). We provide upper and lower bounds on the complexity of implementing these objects in a wait-free manner in the shared memory model.
ISSN:2331-8422